C++キューを使用したBFS
14607 ワード
#include <iostream>
#include <vector>
#include <queue>
// C++ 을 이용한 BFS 구현. 이때 길은 인접행렬로 나타낸다.
// 큐 이용
using namespace std;
vector<vector<int>> adjMatrix = {
{0,1,1,1,0,0,0,0,0},//0
{1,0,0,0,0,0,0,0,0},//1
{1,0,0,0,0,0,0,0,0},//2
{1,0,0,0,1,0,0,0,0},//3
{0,0,0,1,0,0,0,0,0},//4
{0,0,0,0,0,0,1,1,0},//5
{0,0,0,0,0,1,0,1,1},//6
{0,0,0,0,0,1,1,0,0},//7
{0,0,0,0,0,0,1,0,0},//8
};
vector<bool> visited(adjMatrix.size(), false); // 방문했으면 true, 아니면 false 를 가지고 있는 리스트
queue<int> que;
void bfs(int cur) {
que.push(cur);
visited[cur] = true;
while (que.size() != 0) {
int cur = que.front(); // 큐에서 꺼내온 값
que.pop();
for (int i = 0;i<adjMatrix.size(); i++) {
if (adjMatrix[cur][i] == 1 && !visited[i]) { // 방문해본적없는 새로운 인접한 노드면
que.push(i); // 큐에 넣고
visited[i] = true; // 방문표시
}
}
cout << "visit : " << cur << endl;
}
}
void bfsAll() {
for (int i = 0; i < visited.size(); i++) {
if (!visited[i]) bfs(i);
}
}
int main() {
bfs(0);
bfsAll();
return 0;
}
Reference
この問題について(C++キューを使用したBFS), 我々は、より多くの情報をここで見つけました https://velog.io/@yanz/C-큐를-이용한-BFSテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol