[알고리즘] 순회 - 그래프에서의 BFS

순회 - 그래프에서의 BFS

그래프에 대한 첫번째 알고리즘으로 순회(Graph Traversal)에 대해 알아보도록 하겠다.

순회란 그래프의 모든 노드들을 방문하는 일을 말한다.

아주 유명하고 대표적인 방법으로 

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

2) DFS(Depth-First Search) - 깊이우선탐색

두 가지 방법이 있다.

BFS 알고리즘이란 한마디로 말해서

그래프에서 노드들을 동심원의 형태로 방문하는 것이라고 할수있다.

먼저 순회를 위해서 출발점을 지정해야한다.

위의 그림에서 출발점을 S라고 할 때, S에 인접한 노드들을 먼저 방문한다.

이때 인접한 노드들이란, 거리가 1인 노드를 뜻한다.

그리고나서 거리가 2, 3, ... 인 노드들을 차례로 방문한다.

결과적으로 동심원의 형태로 차례로 퍼져나가는 형태를 보인다.

이렇게 넓이가 점점 퍼져나가는 방식이 너비 우선 탐색의 기본 컨셉이다.

너비 우선 탐색은 큐로 구현 할 수있다.

그전에, 너비 우선탐색에 대해 이미 언급한 바가 있는데,

이진 트리에서 레벨 오더 탐색이 BFS의 이진트리 버전이라고 할 수 있기 때문이다.

루트에서 출발해서 루트의 자식 노드들을 방문하고, 이후에 다음 레벨의 노드들을 방문했다.

그러므로 레벨 오더 탐색과 동일하다고 생각하면 된다.

먼저 출발 노드에 이미 방문된 노드 라고 체크를 하고,

이 노드를 큐에 넣고 시작한다.

이 후에는 while문을 돌면서 큐가 빌때까지 해당 연산을 반복해준다.

큐에서 노드를 하나 빼주고(1번노드) 뺀 노드의 인접한 노드중에서 

체크 되지 않은 모든 이웃 노드를 체크하고 그 노드들을 큐에 넣는다.

그 다음은 앞서 언급한것처럼 똑같은 연산을 반복해 주면 된다.

모든 노드를 방문했을 때 큐가 비어있다면 연산이 종료된다.

그래프에서 모든 노드들이 체크되어 있는 상태이다.

어떤 노드를 시작점으로 잡았는지에 따라 방문 순서가 달라질 수 있다.

BFS(G, s)// 그래프 G와 출발 노드 s
    Q <- ø; // 큐를 하나 생성
    Enqueue(Q,s);
    while Q!=ø do
        u <- Dequeue(Q)
        for each v adjacent to u do                                                                     
            if v is unvisited then
                mark v is visited;
                Enqueue(Q,v);
            end;
        end;
    end;
 

다음은 BFS에 대한 슈도 코드이다.

큐를 하나 생성한 후 출발 노드를 넣고

해당 큐가 빌때까지 노드를 체크해주고 인접노드를 방문하고 큐에 넣는 연산을 반복한다.

BFS(G, s)// 그래프 G와 출발 노드 s
    Q <- ø;
    d[v]<-0;
    π[v]<-null;
    Enqueue(Q,s);
    while Q!=ø do
        u <- Dequeue(Q)
        for each v adjacent to u do                                                                      
            if v is unvisited then
                mark v is visited;
                d[v]<-d[u]+1;
                π[v]<-u;
                Enqueue(Q,v);
            end;
        end;
    end;
 

BFS는 그래프의 모든 노드를 방문하는것 이상의 일을 할 수 있는데

바로 최단경로이다.

BFS를 하면 각 노드에 대한 최단 경로의 길이를 구할 수 있다.

왜냐하면, s에서 Li에 속한 노드까지의 최단 경로는 i 이기 때문이다.

따라서, 다음과 같은 입 출력을 구할 수 있다.

입력 : 방향 혹은 무방향 그래프 G = (V,E), 그리고 출발 노드 s가 V에 속할 때

출력 : 모든 노드 v에 대해서

- d(v) = s로 부터 v까지의 최단 경로의 길이(엣지의 개수)

- π(v) = s로부터 v까지의 최단 경로상에서 v의 직전 노드(predecssor)

위의 슈도 코드는 d(v)와 π(v)를 명시한 코드이다.

위의 그림은 d와 π를 계산한 예이다.

이처럼 각 노드 v와 π[v]를 연결하는 에지들로 구성된 트리를 BFS 트리라고 한다. 

위의 그림에서 시작점 s를 루트로 생각했을 때 나머지 노드들이 트리의 모양을 띠고 있다.

BFS 트리의 특징은 모든 엣지들이 동일한 레이어 안에 있거나 하나의 레이어를 건너간다.

PRINT-PATH(G,s,v)
    if v=s then
        print s;
    else if π[v] = null then
        print "no path from s to v exists";                                                               
    else
        PRINT-PATH(G,s,π[v]);
        print v;
    end.

위의 슈도 코드는 최단 경로를 출력 하는 코드이다.

재귀적으로 자신을 호출하여 최단 경로를 출력 하게 된다.

너비 우선 순회는 방향 그래프이거나 disconnected 상태라면 BFS에 의해서 모든 노드가 방문되지 않을수 있다.

따라서 이를 위해서 남은 노드에 대한 추가 연산을 진행해 주어야한다.

예를 들어,

BFS-ALL(G){
    while this exists unvisited node v                                                                    
    BFS(G, v);
}

코드를 따로 호출해서 남은 노드를방문해 준다.