너비우선탐색 BFS

Description

너비우선탐색 BFS(Breadth First Search)은 너비를 우선으로 탐색하는 탐색 알고리즘이다.
주로 최단 경로를 찾을때 사용하며 Queue를 활용하여 구현한다.

dfs 때와 마찬가지로 이러한 그래프 구조의 노드들이 있다고 보자.

동일하게 맨 처음 노드를 queue에 넣어주고 방문 할때마다 방문처리를 해준다.
우선 시작지점인 1을 큐에 넣고 시작한다.

큐에서 1을 제거하고 인접 노드를 탐색한다.
2, 4, 6을 순서대로 방문하고 큐에 넣는다.

가장 먼저 들어온 2를 큐에서 제거하고 인접 노드인 3을 방문한다.
3을 큐에 넣는다.

큐에서 4를 제거하고 인접한 노드 3을 방문할 수 있는지 확인한다.
이미 방문처리가 되었기때문에 다음으로 넘어간다.

큐에서 6을 제거하고 인접 노드인 5를 방문한다.
5를 큐에 넣는다.

큐에서 3을 제거하고 인접 노드를 확인한다.
인접 노드 2와 4는 이미 방문처리가 되었기 때문에 다음으로 넘어간다.

큐에서 5를 제거하고 인접 노드를 확인한다.
인접 노드는 6뿐이나 이미 방문했기 때문에 다음으로 넘어간다.
큐가 비었기 때문에 bfs는 종료된다.

---

Cord

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<int> v[7];
bool visited[7];
queue<int> q;

void bfs(int _start)
{
	// 첫 시작 지점 큐에 넣기
	q.push(_start);
	visited[_start] = true;

	while (!q.empty())
	{
		int current = q.front();
		q.pop();
		cout << current << ' ';

		// v[current]가 가진 간선의 수 만큼 방문 시도 
		for (int i = 0; i < v[current].size(); i++)
		{
			int next = v[current][i];

			if (!visited[next])
			{
				q.push(next);
				visited[next] = true;
			}
		}
	}

	
}

int main()
{
	// 간선 연결
	// 1 <-> 2
	v[1].push_back(2);
	v[2].push_back(1);
	// 1 <-> 4
	v[1].push_back(4);
	v[4].push_back(1);
	// 1 <-> 6
	v[1].push_back(6);
	v[6].push_back(1);
	// 2 <-> 3
	v[2].push_back(3);
	v[3].push_back(2);
	// 3 <-> 4
	v[3].push_back(4);
	v[4].push_back(3);
	// 5 <-> 6
	v[5].push_back(6);
	v[6].push_back(5);

	// bfs 실행
	bfs(1);

	cout << "\n\n\n\n\n\n";

	return 0;
}

---

Result