[Java] 너비 우선 탐색(BFS; Breadth First Search) 개념 및 정리

개념

너비 우선 탐색(BFS; Breadth First Search)은 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘으로,

동작 과정이 직관적이여서 이해하기 쉽다

 

[그림 1] 그래프의 너비 우선 탐색 (출처 : 알고리즘 문제 해결 전략)

(a)의 그래프에서, a를 탐색의 시작점이라고 하자

H0의 a를 방문하고, H1의 b d e h, 그리고 H2, H3에 속한 정점들을 순서대로 방문해 나간다

이를 구현하는 간단한 방법은, 목록에 먼저 넣은 정점을 먼저 꺼내는 것이다

시작점에서 멀리 있는 정점일수록 나중에 목록에 추가되기 때문이다

이 조건을 큐를 사용하여 만족시킬 수 있게 된다

 

---

코드

import java.io.*;
import java.util.*;

class BfsGraph {
    private int nV; // 노드의 개수
    private LinkedList<Integer> adj[]; // 인접 리스트
    
    // 초기화
    BfsGraph(int nV) {
        this.nV = nV;
        adj = new LinkedList[nV];
        for (int i=0; i<nV; ++i)
          adj[i] = new LinkedList();
    }
    
    // 그래프 탐색
    public ArrayList<Integer> bfs(int start) {
        // 노드의 방문 여부 판단 (초깃값: false)
        boolean discovered[] = new boolean[nV];
        // BFS 구현을 위한 큐(Queue) 생성
        LinkedList<Integer> queue = new LinkedList<Integer>();
        // BFS 순서
        ArrayList<Integer> order;
    
        // 현재 노드를 방문한 것으로 표시하고 큐에 push
        discovered[start] = true;
        queue.add(start);
    
        // 큐(Queue)가 빌 때까지 반복
        while (queue.size() != 0) {
            // 방문한 노드를 큐에서 pop하고 값을 출력
            int here = queue.poll();
            // 방문 순서에 add
            order.add(here);
    
            // 방문한 노드와 인접한 모든 노드를 가져온다.
            Iterator<Integer> i = adj[here].listIterator();
            while (i.hasNext()) {
                int there = i.next();
                // 방문하지 않은 노드면 방문한 것으로 표시하고 큐에 삽입(enqueue)
                if (!discovered[there]) {
                    discovered[there] = true;
                    queue.add(there);
                }
            }
        }
        return order;
    }
    
    void put(int u, int v) { adj[u].add(v); }
}

 

DFS와 달리 발견과 방문이 같지 않아 모든 정점은 다음과 같은 3개의 상태를 순서대로 거친다

 

1. 아직 발견 X
2. 발견 O, 방문 X (큐에 저장)
3. 방문까지 O

그리고 BFS에서 새 정점을 발견하는 데 사용했던 간선들만을 모은 트리를

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

 

---

시간 복잡도

이 역시 DFS와 마찬가지다

 

인접 리스트를 이용했을 때,

모든 정점을 한 번씩, 간선을 1번 (무향 그래프일 경우 2번) 확인하므로

O(|V| + |E|) 가 된다

(|V|는 정점 수, |E|는 간선 수)

 

인접 행렬을 사용한다면 dfs() 내부에서 다른 모든 정점들을 순회하며 간선을 확인하므로

O(|V|^2) 가 된다

 

---

최단 경로 알고리즘

BFS는 주로 딱 하나의 용도로 사용되는데, 바로 그래프의 최단 경로 문제이다

가중치가 없는 그래프를 다루도록 해보자

 

BFS를 간단히 변경해 모든 정점에 대해 distance[]를 계산할 수 있다

예를 들어 간선 (u, v)를 통해 distance[v] = distance[u] + 1 임을 알 수 있다

 

코드를 구현해보자

BFS 스패닝 트리를 일반적인 트리, 그래프 형태로 저장하는 대신

각 정점의 부모 번호만으로 표현하여 쉽게 계산할 수 있다

 

public void bfs2(int start, ArrayList<Integer> distance, ArrayList<Integer> parent {
    // -1로 초기화
    for(int i = 0; i < adj.length; i++) {
        distance[i] = -1;
        parent[i] = -1;
    }
    
    LinkedList<Integer> queue = new LinkedList<Integer>();
    distance[start] = 0;
    parent[start] = start;
    queue.add(start);
    while (queue.size() != 0) {
        int here = queue.poll();
        
        Iterator<Integer> i = adj[here].listIterator();
        while (i.hasNext()) {
            int there = i.next();
            
            if (!distance[there]) {
              queue.add(there);
              distance[there] = distance[here] + 1;
              parent[there] = here;
            }
        }
    }
}

public ArrayList<Integer> shortestPath(int v, ArrayList<Integer> parent) {
    ArrayList<Integer> path;
    // 역순으로 부모 찾아 길 따라가기
    while(parent[v] != v) {
        v = parent[v];
        path.add(v);
    }
    // 뒤집기
    Collections.reverse(path);
    return path;
}

 

---

더 나아가기 키워드

• 양방향 탐색
• 점점 깊어지는 탐색(IDS; Iteratively Deepening Search)
• BFS의 최단 경로 문제 알고리즘
  - 다익스트라의 최단 경로 알고리즘
  - 벨만-포드의 최단 경로 알고리즘
  - 플로이드의 모든 쌍 최단 거리 알고리즘
• BFS의 최소 스패닝 트리
  - 프림의 최소 스패닝 트리 알고리즘
  - 크루스칼의 최소 스패닝 트리 알고리즘