C++で「Breadth First Search」(BFS)を使用したバイナリツリーナビゲーション
7511 ワード
1 2
1 3
2 4
2 5
3 6
3 7
上記の入力を使用して、次のバイナリツリーを作成します.
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
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を使用して解凍します.1 2
1 3
2 4
2 5
3 6
3 7
Reference
この問題について(C++で「Breadth First Search」(BFS)を使用したバイナリツリーナビゲーション), 我々は、より多くの情報をここで見つけました https://velog.io/@juwon9733/BFSBreadth-First-search를-활용한-이진트리-탐색-in-Cテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol