반응형
너비 우선 탐색(Breadth First Search, BFS)
너비 우선 탐색이란?
- 임의의 노드에서 인접한 노드를 먼저 모두 탐색하고 다음 단계로 넘어간다.
- 순환 알고리즘의 형태
- 그래프 탐색 시 방문 노드를 반드시 검사해야 한다.
- 두 노드 사이의 최단 경로, 임의의 경로를 탐색할 때 사용한다.
- DFS보다 빠른 탐색 속도를 보인다.
- 큐를 이용하여 구현한다.
너비 우선 탐색 방법
- 1. A노드를 먼저 방문하고, 방문한 노드를 표시한다.
- 2. A노드와 인접한 노드를 큐에 넣고, 해당 노드들을 차례로 방문한다.
- 3. A노드와 인접한 노드를 방문하며 해당 노드와 인접한 노드를 다시 큐에 넣는다.
- 4. 위 과정을 반복하며 모든 노드를 방문한다.
너비 우선 탐색 코드(C++)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
bool visit[6];
// 큐 이용
void BFS(vector<vector<int>> &v,int node)
{
queue<int> q;
visit[node] = true;
q.push(node);
while (!q.empty())
{
node = q.front();
q.pop();
cout << "노드 " << node << " 방문 " << endl;
for (auto index : v[node])
{
// 해당 노드를 방문하지 않았다면 큐에 추가
if (!visit[index])
{
q.push(index);
visit[index] = true;
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
vector<vector<int>> v{ {1},{0,2,5},{1,3,4},{2},{2,5},{1,4} };
BFS(v, 0);
return 0;
}
반응형
'알고리즘 > 알고리즘 이론' 카테고리의 다른 글
최단 거리 알고리즘 - 벨만-포드(Bellman-Ford) 알고리즘 (0) | 2020.11.23 |
---|---|
최단 경로 탐색 알고리즘 - 다익스트라(Dijkstra) (0) | 2020.07.16 |
탐색 알고리즘 - 깊이 우선 탐색(Depth First Search, DFS) (0) | 2020.06.22 |
탐색 알고리즘 - 이분 탐색(Binary Search) (0) | 2020.06.22 |
유니온 파인드(Union - Find) (0) | 2020.06.17 |
댓글