C++で「Breadth First Search」(BFS)を使用したバイナリツリーナビゲーション

7511 ワード

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
  • if(ch[図[x][i]=0):頂点が行ったことのない場所を区別できる.
  • ex)
    1 2
    1 3
    2 4
    2 5
    3 6
    3 7