BFS(Breadth First search)를 활용한 이진트리 탐색 in C++

1 2
1 3
2 4
2 5
3 6
3 7
위와 같은 입력으로 인해 아래의 이진트리가 생성

1. 위와 같은 이진트리를, BFS탐색하는 경우의 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int ch[101];
queue<int> Q;
vector<int> graph[101];
int main() {
	freopen("input.txt", "rt", stdin);
	for(int i=1; i<=6; i++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	Q.push(1);
	ch[1] = 1; 
	while(!Q.empty()) {
		int x = Q.front();
		cout << x << " ";
		Q.pop();
		for(int i=0; i<graph[x].size(); i++) {
			if(ch[graph[x][i]] == 0) {
				ch[graph[x][i]] = 1;
				Q.push(graph[x][i]);	
			}
		}
	}
	return 0;
}

BFS는 queue를 사용하여 풀이하는 것이 일반적이다.

• graph[a].push_back(b), graph[b].push_back(a) : 트리를 그래프로 생각한다면, 방향성이 없는 무방향 그래프이므로 이와 같이 표현하였다.
• for(int i=0; i<graph[x].size(); i++) : 해당 vertex에서 갈 수 있는 곳에 대해서 고려하는 부분이다.
• if(ch[graph[x][i]] == 0) : vertex가 가보지 않은곳에 대해서 구분할 수 있게 한다.

ex)
1 2
1 3
2 4
2 5
3 6
3 7