[c++] 이진트리 넓이우선탐색, 그래프 최단거리 - BFS

이진트리 넓이우선탐색(BFS)

#include <iostream>
#include <vector>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int Q[100], front=-1, back=-1, ch[10];
vector<int> map[10];
int main() {
	freopen("input.txt", "rt", stdin);
	int i, a, b, x;
	for(i=1; i<=6; i++){
		scanf("%d %d", &a, &b);
		map[a].push_back(b);
		map[b].push_back(a);
	}
	Q[++back]=1;
	ch[1]=1;
	while(front<back){
		x=Q[++front];
		printf("%d ", x);
		for(i=0; i<map[x].size(); i++){
			if(ch[map[x][i]]==0){
				ch[map[x][i]]=1;
				Q[++back]=map[x][i];
			}
		}
	}
	return 0;
}

 

그래프 최단거리

#include <iostream>
#include <vector>
#include <queue>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int ch[30], dis[30];
vector<int> map[10];
int main() {
	freopen("input.txt", "rt", stdin);
	int n, m, i, a, b, x;
	vector<int> map[30];
	queue<int> Q;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d", &a, &b);
		map[a].push_back(b);
	}
	Q.push(1);
	ch[1]=1;
	while(!Q.empty()){
		x=Q.front();
		Q.pop();
		for(i=0; i<map[x].size(); i++){
			if(ch[map[x][i]]==0){
				ch[map[x][i]]=1;
				Q.push(map[x][i]);
				dis[map[x][i]]=dis[x]+1;
			}
		}
	}
	for(i=2; i<=n; i++){
		printf("%d : %d\n", i, dis[i]);
	}
	return 0;
}