[그래프] Graph 5: Breadth First Search 그래프의 너비 우선 탐색

1. 그래프의 너비 우선 탐색(Breadth First Search, BFS)

 

 

 

 

 

너비 우선 탐색은 깊이 우선 탐색과 함께 그래프 탐색 방식의 두 축을 이룬다.

 

다익스트라의 최단 거리 알고리즘이나

 

프림의 최소 스패닝 트리 알고리즘에서 BFS가 쓰인다.

 

 

 

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

 

너비 우선 탐색은 각 정점을 방문할 때마다 모든 인접 정점들을 검사한다.

 

이 중 처음 보는 정점을 방문할 때마다 모든 인접 정점들을 검사한다. 

 

이중 처음 보는 정점을 발견하면 이 정점을 방문 예정이라고 기록해둔다.

 

인접한 정점을 모두 검사하고 나면, 지금까지 기록한 목록에서 다음 정점을 꺼내서 방문하게 된다.

 

 

 

따라서 BFS의 방문 순서는 정점의 목록에서 어떤 정점을 먼저 꺼내는지에 의해 결정된다.

 

탐색을 수행하면서 각 정점과 연결된 것을 계속 집어넣는다, 만약 집어넣은것을 바로 꺼내서 방문하게되면

 

이전에 조사했던 정점의 시작점과의 거리가 동일한 정점들을 조사를 아직 하지 않았을 확률이 높다.

 

하지만 만약 목록에 먼저 넣은 정점을 항상 먼저 꺼내는 자료 구조인 큐를 사용하게되면

 

항상 멀리있는 정점일수록 나중에 목록에 추가되기 때문에 너비 우선 탐색의 조건을 만족시킬 수 있다.

 

스패닝 트리

또한 DFS처럼 BFS에서 새 정점을 발견하는 데 사용했던 간선들만을 모은 트리를

 

너비 우선 탐색 스패닝 트리 (BFS Spanning Tree) 라고 한다

 

 

 

2. 너비 우선 탐색의 시간 복잡도

 

vector<vector<int> > adj;
vector<int> bfs(int start)
{
    vector<bool> discovered(adj.size(), false);
    queue<int> q;
    vector<int> order;
    discovered[start] = true;
    q.push(start);
 
    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])
            {
                q.push(there);
                discovered[there] = true;
            }
        }
    }
    return order;
}

 

BFS는 발견과 방문이 같지 않다.

따라서 세 개의 상태를 순서대로 거쳐 가게 된다.

 

1. 아직 발견되지 않은 상태

2. 발견되었지만 아직 방문되지는 않은 상태(이 상태에 있는 정점들의 목록은 큐에 저장되어있다.)

3. 방문된 상태

 

이렇게 DFS처럼 정점을 한 번씩 방문하여, 정점을 방문할 때마다 인접한 모든 간선을 검사하기 때문에

 

인접 리스트로 구현된 경우 O(|V| + |E|) , 인접 행렬로 구현했을 경우 O(|V|^2) 의 시간 복잡도를 가진다.

 

 

 

 

3. 너비 우선 탐색과 최단 거리: 가중치가 없는 그래프

 

그래프의 구조에 관련된 다양한 문제를 푸는 데 사용되는 깊이 우선 탐색과 달리,

 

너비 우선 탐색은 대개 최단 경로 문제를 해결할 때 많이 쓴다.

 

 

최단 경로 문제는 두 정점을 연결하는 경로 중 가장 길이가 짧은 경로를 찾는 문제로,

 

그래프 이론의 가장 고전적인 문제 중 하나이다.

 

 

경로의 길이를 경로에 포함된 간선의 갯수라고 정의하면

 

BFS를 간단하게 변경해 모든 정점에 대해 시작점으로 부터의 거리 distance[]를 계산하도록 할 수 있다.

 

BFS과정에서 간선 (u, v)를 통해 정점 v를 처음 발견해 큐에 넣었다고 해보자

 

distance[v] = distance[u] + 1

 

그러면 시작점에서 v까지의 길이는  시작점에서 u까지의 길이에 1 늘어난것이 된다.

 

 

이것은 다음과 같이 증명할 수 있다

 

1. distance[v] 가  distance[u] + 1 보다 클 수 없음은 분명하다.

  시작점-> u 까지의 경로에 (u,v)를 덧붙이면 distance[u] + 1이 되기 때문이다

 

2. distance[v] 가  distance[u] + 1 보다 작을 수 없는것도 당연하다

   더 짧다고 가정해보자, 그러면 u말고 거리가 시작점에 더 가까운 정점이 v와 연결되어 있다는 것이다

  그러면 이 정점은 u 전에 발견되었어야 하며, 따라서 (u, v)를 통해 v를 처음 발견했다는 가정과 모순이 생긴다.

 

 

 

 

이러한 bfs의 속성의 또 다른 중요한 의미는 시작점으로 부터 다른 모든 정점까지의 최단 경로를 

 

너비 우선 탐색 스패닝 트리 위에서 찾을 수 있다는 것이다.

 

각 정점으로 부터 트리의 루트인 시작점으로 가는 경로가 실제 그래프 상에서의 최단 경로라는 것이다.

 

 

다음은 최단 경로를 계산하는 너비 우선 탐색의 구현이다

 

여기서는 스패닝 트리를 각 정점의 부모 번호만으로 표현하였다.

 

 

 

void bfs2(int srart, vector<int>& distance, vector<int>& parent)
{
    distance = vector<int>(adj.size(), -1);
    parent = vector<int>(adj.size(), -1);
 
    queue<int> q;
    distance[start] = 0;
    parent[start] = start;
    q.push(start);
    while(!q.empty())
    {
        int here = q.front();
        q.pop();
        for(int i = 0; i < adj[here].size(); i++)
        {
            int there = adj[here][i];
            if(distance[there] == -1)
            {
                q.push(there);
                distance[there] = distance[here] + 1;
                parent[there] = here;
            }
        }    
    }
}

vector<int> shortestPath(int v, const vector<int>& parent)
{
    vector<int> path(1, v);
    while(parent[v] != v)
    {
        v = parent[v];
        path.push_back(v);
    }
    reverse(path.begin(), path.end());
    return path;
}

 

- 알고리즘 문제해결전략 881p

 

[그래프] SORTGAME Sorting Game