탐색 알고리즘 - 너비 우선 탐색(Breadth First Search, BFS)

너비 우선 탐색(Breadth First Search, BFS)

 

너비 우선 탐색이란?

 

 - 임의의 노드에서 인접한 노드를 먼저 모두 탐색하고 다음 단계로 넘어간다.

 

 - 순환 알고리즘의 형태

 

 - 그래프 탐색 시 방문 노드를 반드시 검사해야 한다.

 

 - 두 노드 사이의 최단 경로, 임의의 경로를 탐색할 때 사용한다.

 

 - DFS보다 빠른 탐색 속도를 보인다.

 

 - 큐를 이용하여 구현한다.

 

---

 

너비 우선 탐색 방법

 

 - 1. A노드를 먼저 방문하고, 방문한 노드를 표시한다.

 

 - 2. A노드와 인접한 노드를 큐에 넣고, 해당 노드들을 차례로 방문한다.

 

 - 3. A노드와 인접한 노드를 방문하며 해당 노드와 인접한 노드를 다시 큐에 넣는다.

 

 - 4. 위 과정을 반복하며 모든 노드를 방문한다.

 

 

 

1. 노드 0 ~ 5인 그래프가 주어졌다.

 

2. 노드 0을 탐색한 후 인접한 노드 1를 탐색한다.

3. 노드 1과 인접한 노드 2를 탐색한다

4. 노드 1과 인접한 노드 5를 탐색한다

 

5. 노드1과 인접한 노드가 없기 때문에 노드 2와 인접한 노드 3을 탐색한다

 

6. 노드 2와 인접한 노드 4를 탐색한다

 

 

7. 모든 노드 탐색 결과

 

---

 

너비 우선 탐색 코드(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;
}

 

 

실행 결과