그래프 탐색 알고리즘 (3) BFS 를 중심으로

1. 들어가기

지난 글에 이어 그래프 탐색 알고리즘에 대해서 다뤄볼 것이다. 이번 글에서는 너비 우선 탐색(BFS;Breadth First Search)을 다뤄보겠다. 너비 우선 탐색은 시작 점으로부터 트리와 가까운 꼭짓점을 모두 탐색한 뒤, 먼 꼭짓점까지 확장하는 규칙을 가지고 있다. 이와 관련해서 좀 더 자세하게 알아보자.
 
 

2. 너비 우선 탐색

너비 우선 탐색은 시작점으로부터 인접한 꼭짓점을 모두 탐색하고, 인접한 꼭짓점을 시작으로 다시 인접한 꼭짓점들을 탐색하는 탐색이다. 다시 말하면, 깊이가 1씩 증가함에 따라 시작점과 가장 가까운 노드들을 모두 탐색하는 기법이라고 볼 수 있다. 깊이 우선 탐색의 시작점을 기준으로 최대 깊이를 우선으로 탐색하는 기법과는 대조적이다. 너비 우선 탐색도 예시를 통해 알아보겠다.
 

그래프

위 그래프는 깊이 우선 탐색의 예시에서도 봤었다. 위 그래프를 너비우선 탐색으로 탐색한다면 다음과 같이 탐색할 수 있을 것이다.
(1) 시작 노드 A와 인접하고, 아직 탐색되지 않은 꼭짓점과 B, C가 있을 때, 사전적으로 앞에 오는 B부터 탐색하고, C를 탐색한다.
      A - B - C
(2) B와 인접하고 탐색되지 않은 꼭짓점 D와 E가 있을 때, 사전적 순서가 더 빠른 D를 먼저 선택한다.
      A - B - C - D - E
(3) C와 인접하고 탐색되지 않은 꼭짓점이 없다.
(4) D와 인접하고 탐색되지 않은 꼭짓점이 없다.
(5) E와 인접하고 탐색되지 않은 F를 탐색한다.
    A - B - C - D - E - F
(6) F와 인접하고 탐색되지 않은 G를 탐색한다.
    A - B - C - D - E - F - G
(7) G와 인접하고 탐색되지 않은 H를 탐색한다.
    A - B - C - D - E - F - G - H
(8) 모든 꼭짓점을 탐색했으므로 탐색을 종료한다.
 
너비 우선 탐색 과정을 그래프로 나타내면 다음 그림과 같다.

BFS 탐색 경로를 나타낸 그래프

 

 

3. 정리

너비 우선 탐색 과정을 정리하면 다음과 같다.
1) 시작점 n을 탐색
2) 시작점에 인접한 꼭짓점 들 중 탐색하지 않은 n에 인접한 꼭짓점을 모두 탐색
3) 모든 꼭짓점이 탐색됐으면, 이전에 탐색한 꼭짓점을 n으로 하여 탐색하지 않은 인접한 꼭짓점을 모두 탐색
4) 그래프의 모든 꼭짓점을 탐색할 때까지 반복
 
 

4. 구현

public class Main {
    static int[][] graph;
    static boolean[] visited;
    static int N, M; // N=꼭짓점 수, M=간선 수
    static StringBuffer sb;
    
    public static void bfs(int v){
        Queue queue = new LinkedList();
        queue.add(v);
        visited[v] = true;
        while(!queue.isEmpty()){
            int cur = (int) queue.poll();
            sb.append(Character.toString(cur+65) + " ");
            for(int i=0; i<=N; i++){
                if(!visited[i]){
                    if(graph[cur][i] == 1){
                        queue.add(i);
                        visited[i] = true;
                    }
                }
            }
        }
    }

    public static void main(String[] args){
        char[] p1 = new char[]{'A', 'A', 'B', 'B', 'C', 'E', 'F', 'G'};
        char[] p2 = new char[]{'B', 'C', 'D', 'E', 'E', 'F', 'G', 'H'};

        N = 8;
        M = 8;

        visited = new boolean[N+1];
        graph = new int[N+1][N+1];
        sb = new StringBuffer();

        for(int i=0; i<M; i++){
            int a = Character.valueOf(p1[i]) - 65;
            int b = Character.valueOf(p2[i]) - 65;

            graph[a][b] = 1;
            graph[b][a] = 1;
        }

        bfs(0);
        System.out.println(new String(sb)); // A B C D E F G H 
    }
}

 
 

5. BFS 구현 시 고려해야 할 사항

- 너비우선탐색의 경우에도 불필요한 탐색이 포함될 수 있다. 그런 경우에는 방문을 확인하는 배열을 통해 방문 여부를 체크하면서 불필요한 탐색 횟수를 줄인다.
- 너비 우선 탐색은 시작 점으로부터 얼마만큼 떨어져 있는 지를 단계적으로 탐색할 때 사용하기 좋은 방법이다. 다음과 같이 경로를 탐색할 때 사용하기 좋다는 것을 염두해두자.
예) 악당으로부터 얼마만큼 떨어져 있는 지에 대해 탐색하는 경우

 
참고문헌 : 컴퓨팅 사고력을 키우는 이산수학 / 한빛아카데미