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;
}