그래프 탐색 - BFS

BFS

BFS는 시작 정점에서 가까운 정점부터 순서대로 방문하는 그래프 탐색 알고리즘이다. 이러한 탐색 방식으로 시작 정점에서 각 정점들을 최단 경로로 방문한다.

 

아래는 인접 행렬을 탐색하는 BFS 코드이다.

static void BFS(int start, int[][] graph, boolean[] discovered) {
        Queue<Integer> queue = new LinkedList<>();
        discovered[start] = true;
        queue.add(start);

        while(!queue.isEmpty()) {
            int v = queue.remove();
            for(int i=0; i<graph.length; i++) {
                if(graph[v][i] == 1 && !discovered[i]) {
                    discovered[i] = true;
                    queue.add(i);
                }
            }
        }
    }

깊이 우선 탐색과는 달리 너비 우선 탐색에서는 발견과 방문이 같지 않다. 모든 정점은 다음과 같은 상태를 순서대로 거쳐 간다.

1. 아직 발견되지 않은 상태
2. 발견되었지만 아직 방문되지는 않은 상태 (큐에 저장된 상태)
3. 방문된 상태 (큐에서 나온 상태)

BFS 시간 복잡도

BFS는 정확히 정점의 개수(V) 만큼 호출된다. BFS의 성능은 인접 간선을 검사하는 for문에 의해 지배되므로 인접 리스트에서의 BFS 시간 복잡도는 O(V + E)가 되며 인접 행렬에서의 BFS 시간 복잡도는 O(V²)가 된다.

BFS와 최단 경로

BFS도 DFS와 같이 탐색에 사용된 간선들만 모아 보면 아래와 같은 너비 우선 탐색 스패닝 트리를 얻을 수 있다.

너비 우선 탐색 스패닝 트리

위 그림을 보면 시작 정점에서 각 정점을 잇는 경로가 최단 경로(두 정점을 연결하는 경로 중 가장 길이가 짧은 경로)임을 알 수 있다. 즉 시작 정점에서 각 정점까지 최단 경로로 방문하는 알고리즘이 BFS 알고리즘이다. 그래서 그래프 구조와 관련된 다양한 문제를 푸는데 사용되는 DFS와 달리 BFS는 대게 최단 경로 문제를 푸는데 사용된다.

 

아래는 시작점에서 각 정점까지의 최단 거리와, 최단 경로를 구하는 코드이다. 각 정점까지의 최단 거리와 너비 우선 탐색 스패닝 트리를 계산하는 bfs2()와, 너비 우선 탐색 스패닝 트리를 입력 받아 최단 경로를 반환하는 shortestPath()의 구현이다.

//graph - 인접 행렬(그래프)
//distance - 시작 정점에서 각 정점까지 가는 최단 거리 (처음 -1로 초기화되어 있음)
//parent - 너비 우선 탐색 스패닝 트리, 각 노드는 부모 노드의 포인터를 가짐
static void bfs(int start, int[][] graph, int[] distance, int[] parent) {
    Queue<Integer> queue = new ArrayDeque<>();
    distance[start] = 0;
    parent[start] = start;
    queue.add(start);

    while(!queue.isEmpty()) {
        int v = queue.poll();

        //distance[i]가 -1이면 i 정점은 아직 발견되지 않은 정점
        for(int i=0; i<graph.length; i++) {
            if(graph[start][i] == 1 && distance[i] == -1) {
                distance[i] = distance[start] + 1;
                parent[i] = start;
                queue.add(i);
            }
        }
    }
}

//v부터 시작 정점까지의 최단 경로 반환
//너비 우선 탐색 스패닝 트리에서 v에서 시작 정점까지의 경로가 최단 경로
static List<Integer> shortestPath(int v, int[] parent) {
    ArrayList<Integer> list = new ArrayList<>();

    while(v != parent[v]) {
        list.add(v);
        v = parent[v];
    }
    list.add(v);
    Collections.reverse(list);
    return list;
}