[c++] 너비 우선 탐색(BFS) 그래프 탐색 알고리즘
그래프는 정점과 그 정점을 연결하는 간선으로 이뤄진 자료구조입니다. 너비 우선 탐색 (Breadth-First Search, BFS)은 그래프를 탐색하고 특정한 시작정점으로부터 가까운 정점들부터 탐색하는 알고리즘입니다.
알고리즘 동작 원리
BFS 알고리즘은 큐를 이용하여 동작합니다. 시작 정점을 큐에 넣고 방문했다고 표시합니다. 그 후, 해당 정점과 인접한 정점들을 큐에 넣고 방문했다고 표시합니다. 이후 큐에서 하나의 정점을 빼고, 해당 정점과 인접한 정점들을 큐에 넣고 방문했다고 표시하는 과정을 반복합니다.
이렇게 하면 시작 정점으로부터 가까운 정점부터 탐색하게 되어있으며, 최단 경로를 찾는 데에 사용될 수 있습니다.
예시 코드
#include <iostream>
#include <queue>
#include <vector>
void bfs(std::vector<std::vector<int>> graph, int start) {
std::queue<int> q;
std::vector<bool> visited(graph.size(), false);
q.push(start);
visited[start] = true;
while (!q.empty()) {
int current = q.front();
q.pop();
std::cout << "Visited: " << current << std::endl;
for (int i = 0; i < graph[current].size(); i++) {
if (graph[current][i] == 1 && !visited[i]) {
q.push(i);
visited[i] = true;
}
}
}
}
int main() {
std::vector<std::vector<int>> graph = {{0, 1, 1, 0},
{1, 0, 0, 1},
{1, 0, 0, 1},
{0, 1, 1, 0}};
bfs(graph, 0);
return 0;
}
위의 코드는 인접행렬로 표현된 그래프에서 BFS 알고리즘을 구현한 것입니다.
결론
BFS 알고리즘은 그래프를 탐색하며, 시작 정점으로부터의 최단 경로를 찾는 데 사용됩니다. 큐를 이용하여 동작하며, 인접한 정점들을 너비 우선으로 탐색합니다. 이를 통해 특정 문제에 대한 최적의 해답을 찾을 수 있습니다.