그래프의 너비 우선 탐색

너비 우선 탐색(BFS)는 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘이다.

너비 우선 탐색은 깊이 우선 탐색과는 달리 발견과 방문이 같지 않다.

1. 아직 발견되지 않은 상태 ( 큐에 넣기 전)

2. 발견되었지만 아직 방문되지 않은 상태 ( 큐에서 대기 중)

3. 방문된 상태 ( 큐에서 꺼낸다 )

너비 우선 탐색이 시작점인 0 을 방문하면 정점 1 3 4 8이 목록에 추가 된다. 이들은 모두 0에서 간선 하나로 연결되기에

어느 정점을 먼저 꺼내도 상관 없다. 이 중 1을 꺼내 방문했다고 하면 2가 목록에 추가 된다. 이때 2는 자신보다 먼저 목록에 추가된

남은 정점 3 4 8이 방문되기 전까지는 결코 방문되어서는 안된다. 이를 구현하는 방법은 목록에 먼저 넣은 정점을 항상 먼저 꺼내야 하고

이는 큐를 사용하면 너비 우선 탐색의 조건을 만족 시킬 수 있다.

코드 ( C++ )

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

vector<vector<int>> adj;

vector<int> bfs(int start)

{

vector<bool> discovered(adj.size(), false);

queue<int> q;

// 정점의 방문 순서

vector<int> order;

q.push(start);

discovered[start] = 1;

while (!q.empty())

{

int here = q.front();

q.pop();

order.push_back(here);

for (int i = 0; i < adj[here].size(); ++i)

{

int there = adj[here][i];

if (!discovered[there]) {

discovered[there] = true;

q.push(there);

}

}

}

return order;

}

int main()

{

//정점의 수

int V = 9;

adj = vector<vector<int>>(V, vector<int>());

adj[0].push_back(1);

adj[0].push_back(3);

adj[0].push_back(4);

adj[0].push_back(8);

adj[1].push_back(0);

adj[1].push_back(2);

adj[1].push_back(3);

adj[2].push_back(1);

adj[2].push_back(5);

adj[2].push_back(6);

adj[3].push_back(0);

adj[3].push_back(1);

adj[3].push_back(6);

adj[4].push_back(5);

adj[4].push_back(0);

adj[5].push_back(4);

adj[5].push_back(2);

adj[6].push_back(2);

adj[6].push_back(3);

adj[6].push_back(7);

adj[7].push_back(6);

adj[8].push_back(0);

vector<int> ret;

ret = bfs(0);

// 방문 순서

for (int i = 0; i < ret.size(); ++i)

cout << ret[i] << " ";

return 0;

}

참고 문헌 : 알고리즘 해결 전략