[Algorithm] BFS : 너비 우선 탐색(Java)

DFS와 함께 가장 널리 사용되는 그래프 탐색 알고리즘인 너비 우선 탐색(Breadth First Search, BFS)에 대해 알아보자.

다익스트라(Dijkstra) 알고리즘이나 최소 스패닝 트리를 찾는 프림(Prim) 알고리즘 등이 BFS를 기반으로 하고 있다.

---

동작 과정

BFS는 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘이기 때문에 DFS에 비해 매우 직관적이다. 

위의 그래프를 보자.

a를 탐색의 시작점이라 하면, a에서부터 최소 몇 개의 간선을 지나야 도달할 수 있는가를 기준으로 그래프의 정점들을 나눌 수 있다. 간선 $i$개 지나야 도착할 수 있는 정점의 집합을 $H_i$라고 부르자. 그러면 BFS는 $H_0$에 속한 a를 가장 먼저 방문하고, 그 후 $H_1, H_2$ 그리고 $H_3$에 속한 정점들을 순서대로 방문해 나갈 것이다. 각 정점과 시작점 사이에 경로가 두 개 이상인 경우, 그중 최단 경로가 방문 순서를 결정하게 된다. 예를 들어 정점 b나 d는 a와 길이 1인 경로로도 연결되어 있고, 2인 경로로도 연결되어 있지만 둘 다 $H_1$에 속한다.

 

어떻게 이와 같은 특성을 갖는 탐색 알고리즘을 만들었을까?

BFS는 각 정점을 방문할 때마다 모든 인접 정점들을 검사한다. 이 중 처음 보는 정점을 발견하면 이 정점을 방문 예정이라고 기록해 둔 뒤, 별도의 위치에 저장한다. 인접한 정점을 모두 검사하고 나면, 지금까지 저장한 목록에서 다음 정점을 꺼내서 방문하게 된다. 따라서 BFS의 방문 순서는 정점의 목록에서 어떤 정점을 먼저 꺼내는지에 의해 결정된다. 

 

위의 그래프를 예시로 어떤 순서로 정점을 꺼내야 할지 살펴보자.

BFS의 시작점인 a를 방문하고 나면 정점 b,d,e,h가 목록에 추가된다. 이들은 모두 a에서 간선 하나로 연결되어 있기 때문에, 어느 정점을 먼저 꺼내서 방문해도 상관 없다. 이 중 b를 꺼내 방문했다고 하면 c가 목록에 추가된다. 이때 c는 자신보다 먼저 목록에 추가된 남은 정점 d, e, h가 전부 방문되기 전까지는 결코 방문되어서는 안 된다. 

이를 구현하는 간단한 방법은, 목록에 먼저 넣은 정점을 항상 먼저 꺼내는 것이다. 시작점에서 멀리 있는 정점일수록 나중에 목록에 추가되기 때문이다.

따라서 이를 구현하기 위해서 BFS는 Queue(큐)를 사용한다.

구현

BFS를 자바 코드로 구현하면 다음과 같다. 

public static boolean[] discovered = new boolean[10];//임의의 값
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<>>();

public static void BFS(int start){
	Queue<Integer> queue = new LinkedList<>();
	queue.offer(start);

	discovered[start] = true; //현재 노드 방문처리
	
	while(!queue.isEmpty()){
		int x = queue.poll(); //큐에서 원소 하나 뽑기
		System.out.print(x + " ");

		//해당 원소와 연결된 아직 방문하지 않은 노드를 큐에 삽입
		for(int i=0;i<graph.get(x).size();i++){
			int y = graph.get(x).get(i);
			if(!discovered[y]){
				queue.offer(y);
				discovered[y] = true;
			}
	}
}

여기서 주의할 점은 DFS에서는 visited[]가 각 정점의 방문 여부를 저장했던 것에 비해, BFS의 discovered[]는 각 정점의 발견 여부를 저장한다. 

DFS와 달리 BFS에서는 발견과 방문이 같지 않다. 따라서 모든 정점은 다음과 같은 세 개의 상태를 순서대로 거쳐 가게 된다.

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

BFS에서 새 정점을 발견하는 데 사용했던 간선들만을 모은 트리를 BFS Spanning Tree라 부른다. 아래 그림의 그래프가 위 그래프의 스패닝 트리가 된다.

BFS의 시간 복잡도

DFS와 다를 것이 없다. 모든 정점들을 한 번씩 방문하며, 정점을 방문할 때마다 인접한 모든 간선을 검사하기 때문에,

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

 

BFS와 최단 거리

그래프의 구조에 관련된 다양한 문제를 해결하는 데 사용되는 DFS와 달리, BFS는 딱 하나의 용도로 사용된다. 바로 그래프에서 최단 경로 문제를 해결할 때이다. 지금은 가중치가 없는 그래프를 다루고 있기 때문에, 경로의 길이를 경로에 포함된 간선의 개수라고 정의하도록 하겠다.

 BFS를 간단하게 변경해 모든 정점에 대해 시작점으로부터의 거리 $distance[]$를 계산하도록 할 수 있다. BFS 과정에서 간선 $(u, v)$를 통해 정점 v를 처음 발견해 큐에 넣었다고 하자. 이때 시작점으로부터 v까지의 최단 거리 $distance[v]$는 시작점으로부터 u까지의 최단 거리 $distance[u]$에 1을 더한 것이다. 즉, $distancev[v] = distance[u] + 1$이다.

 이 속성의 또 다른 중요한 의미는 시작점으로부터 다른 모든 정점까지의 최단 경로를 BFS Spanning Tree에서 찾을 수 있다는 것이다. 위의 스패닝 트리를 다시 살펴보면, 각 정점으로부터 트리의 루트인 시작점으로 가는 경로가 실제 그래프 상에서의 최단 경로임을 알 수 있다.

구현

BFS의 스패닝 트리를 일반적인 트리나 그래프 형태로 저장하는 대신 각 정점의 부모 번호만으로 표현한다. 시작점으로부터의 최단 경로는 BFS Spanning Tree에서 루트로 가는 경로이므로, 각 정점이 부모의 번호를 갖고 있게 하면 쉽게 최단 경로를 계산할 수 있다.

//distance[i] = start부터 i까지의 최단 거리
public static int[] distance = new int[10];//임의의 값
//parent[i] = i의 부모의 번호
public static int[] parent = new int[10];
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<>>();

//각 정점까지의 최단 거리와 스패닝 트리 계산
public void BFS2(int start){
    Arrays.fill(distance, -1);
    Arrays.fill(parent, -1);//모두 -1로 초기화

    Queue<Integer> queue = new LinkedList<>();
    distance[start] = 0;
    parent[start] = start; //루트인 경우 자신의 번호
    queue.offer(start);

    while(!queue.isEmpty()){
        int cur = queue.poll(); //큐에서 원소 하나 뽑기

        //해당 원소와 연결된 아직 방문하지 않은 노드를 큐에 삽입
        for(int i=0;i<graph.get(cur).size();i++){
            int next = graph.get(cur).get(i);
            if(distance[next]==-1){
                queue.offer(next);
                distance[next] = distance[cur] + 1;
                parent[next] = cur;
            }
        }
    }
}

//v로부터 시작점까지의 최단 경로를 계산
public ArrayList<Integer> shortestPath(int v){
    ArrayList<Integer> path;

    while(parent[v]!=v){
        v = parent[v];
        path.add(v);
    }
    
    //뒤집기
    Collections.reverse(path);
    
    return path;
}

---

그래프 전체의 구조에 관한 정보를 얻기 위해 사용되는 DFS와 달리, BFS는 대게 시작점으로부터 다른 정점들까지의 거리를 구하기 위해 사용된다. 따라서 DFS에서처럼 모든 정점을 검사하면서 탐색을 수행하는 작업은 잘하지 않는다.