너비 우선 탐색

너비 우선 탐색 알고리즘은 정점 s로부터 거리가 k + 1인 정점을 만나기 전에 s로부터 거리가 k인 정점을 모두 발견하는 알고리즘입니다.

기본 구현

void bfs(int s)
{
    std::queue<int> q;
    q.push(s);
    visited[s] = true;

    while (!q.empty()) {
        int a = q.front();
        q.pop();
        for (auto b : adj[a]) {
            if (visited[b]) {
                continue;
            }
            visited[b] = true;
            q.push(b);
        }
    }
}

기본적인 구현 모습은 위와 같습니다.

시작 정점 s를 큐에 넣고 방문 표시를 합니다.

큐기 빌 때까지 반복문을 돌면서 방문하지 않은 인접한 모든 정점을 방문하게 됩니다.

분석

총 정점의 개수를 $V$, 총 간선의 개수를 $E$라고 할 때,

각 정점이 큐에 들어갔다가 나오는 것이 최대 한 번 이므로 총 시간은 $O(V)$ 시간이 걸립니다.

그리고 각 정점이 큐에서 제거될 때 자신의 인접 리스트를 스캔하는데 모든 간선이 최대 한 번만 스캔 됨이 보장되므로 총 시간은 $O(E)$시간이 걸립니다.

따라서 BFS를 수행하는데 걸리는 시간은 $O(V + E)$ 시간이 걸리게 됩니다.

응용 구현

최단 거리

void bfs(int s)
{
    std::queue<int> q;
    q.push(s);
    visited[s] = true;
    dist[s] = 0;

    while (!q.empty()) {
        int a = q.front();
        q.pop();
        for (auto b : adj[a]) {
            if (visited[b]) {
                continue;
            }
            visited[b] = true;
            dist[b] = dist[a] + 1;
            q.push(b);
        }
    }
}

정점 s에서 도달 가능한 모든 정점으로 가는 최단 거리는 dist 배열을 확인하여 알 수 있습니다.

도달 가능하지 않은 배열의 값을 나타내기 위해서 초기 dist의 모든 값은 무한대로 설정해야 합니다.

최단 경로

정점 s에서 정점 v로 가는 최단 거리 뿐만 아니라 최단 경로도 구할 수 있습니다.

void bfs(int s)
{
    std::queue<int> q;
    q.push(s);
    visited[s] = true;
    parent[s] = -1;

    while (!q.empty()) {
        int a = q.front();
        q.pop();
        for (auto b : adj[a]) {
            if (visited[b]) {
                continue;
            }
            visited[b] = true;
            parent[b] = a;
            q.push(b);
        }
    }
}

정점 a에서 정점 b로 탐색을 진행했다면, parent[b] = a로 설정하여 어디서 출발했는지 기록해둡니다.

이를 진행하기에 앞서 parent의 값은 모두 -1로 설정해둡니다.

parent 값이 -1이라는 의미는 시작 정점이거나 시작 정점에서 도달하지 못했다는 의미입니다.

void printPath(std::vector<int>& parent, int s, int v)
{
	if (s == v) {
		std::cout << s << ' ';
	} else if (parent[v] == -1) {
		// s에서 v로 가는 경로가 없습니다.
		// 여기서 확인하지 말고 dist[v]를 통해 먼저 경로가 존재하는지 확인하고 
		// printPath를 호출하면 신경쓰지 않아도 되는 부분입니다.
	} else {
		printPath(parent, s, parent[v]);
		std::cout << v << ' ';
	} 
}

경로를 출력하기 위해서 재귀 함수를 사용합니다.

printPath(parent, s, v)를 호출하여 s에서 v로 가는 경로를 출력할 수 있습니다.