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

이번에 배워볼 알고리즘은 너비 우선 탐색(Breadth First Search)이다. 줄여서 흔히 BFS라고 부른다. 깊이 우선 탐색은 깊이를 우선시하였다면 너비 우선 탐색은 너비를 우선시하는 탐색 방법이다.

또한, 노드에서 다른 노드로 가는 최단 경로를 구할 때 깊이 우선 탐색은 한 노드의 끝까지 탐색하기 때문에 최단 경로를 보장해 주지 않지만 너비 우선 탐색은 항상 같은 깊이 내에 있는 모든 노드들을 탐색하기 때문에 최단 경로를 보장해 준다는 장점이 있다.

​깊이 우선 탐색은 스택(Stack)을 이용하여 구현하였다면, 너비 우선 탐색은 큐(Queue)를 이용해서 구현한다.

​

너비 우선 탐색의 원리는 다음과 같다.

• 큐에서 노드 하나를 꺼낸다.
• 큐에서 꺼낸 노드에 인접한 노드들 중 아직 방문하지 않은 모든 노드를 방문 표시를 하고 차례대로 큐에 넣어준다. 깊이 우선 탐색은 한 개의 노드만 넣어주는 반면, 너비 우선 탐색은 모든 자식 노드를 큐에 넣어준다.

​

이 과정을 큐에 노드가 없어질 때까지 반복해 주면 된다. 너비 우선 탐색 또한 글보다 그림으로 이해하는 것이 쉽다. 예를 들어 다음 그림과 같은 그래프가 있다고 하자.

 

위 그래프에서 너비 우선 탐색으로 모든 노드를 탐색하는 과정을 살펴보자. 0번 노드에서 시작을 하고 방문 순서는 구현하기 나름이지만 자식 노드들 중 숫자가 낮은 노드를 먼저 탐색하도록 하겠다.

먼저 방문하는 0번 노드를 큐에 담아준다. 또한, 우리는 모든 노드를 한 번만 탐색할 것이기 때문에 중복 탐색을 방지하기 위해 방문했다는 표시를 해준다.

 

큐에서 0번 노드를 빼주고 0번 노드에 인접한 노드들 중 방문하지 않은 1, 2, 3번 노드들을 방문 표시한 후 차례대로 큐에 넣어준다.

 

큐에서 1번 노드를 빼주고, 1번 노드에 인접한 노드들 중 방문하지 않은 4, 5번 노드들을 방문 표시한 후 차례대로 큐에 넣어준다.

 

큐에서 2번 노드를 빼주고, 2번 노드에 인접한 노드들 중 방문하지 않은 6번 노드를 방문 표시한 후 큐에 넣어준다.

 

큐에서 3번 노드를 빼주고, 3번 노드에 인접한 노드들 중 방문하지 않은 7번 도드를 방문 표시한 후 큐에 넣어준다.

 

모든 노드들을 방문하였기 때문에 큐에 남아 있는 노드들을 제거해주고 탐색을 종료한다.

 

너비 우선 탐색으로 방문한 순서는 큐에서 제거한 노드의 순서와 같다. 따라서 0번 노드를 기준으로 그래프를 탐색한 순서 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7이다. 어떻게 구현하기에 따라 방문순서가 조금 바뀔 수는 있지만, 원리는 똑같기에 그래프의 모든 노드를 방문하게 된다.

너비 우선 탐색도 마찬가지로 그래프의 모든 간선을 조사하므로 정점의 수가 n이고 간선의 수가 e인 그래프를 너비 우선 탐색하는 시간은 그래프가 인접 행렬로 구현되었다면 O(n^2)​O(n^2)의 시간 복잡도를 가지며, 인접 리스트로 구현되어 있다면 O(n+e)의 시간 복잡도를 가진다.

​

다음은 Java로 구현한 BFS 알고리즘이다.

import java.util.LinkedList;
import java.util.Queue;

class MyGraph {
	int vertexCnt;
	int[][] m;
	boolean[] visit;
	
	public MyGraph(int N) {
		vertexCnt = N;
		m = new int[N][N];
		visit = new boolean[N];
	}
	
	public void makeUndirectedEdge(int from, int to) {
		m[from][to] = 1;
		m[to][from] = 1;
	}

	public void bfs(int v) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(v);
		visit[v] = true;
		
		while (!q.isEmpty()) {
			int now = q.poll();
			System.out.print(now + " ");
			
			for (int i = 0; i < vertexCnt; ++i) {
				if (m[now][i] == 1 && !visit[i]) {
					visit[i] = true;
					q.offer(i);
				}
			}
		}
	}
}

public class Blog {

	public static void main(String[] args) {
		MyGraph mg = new MyGraph(8);
		mg.makeUndirectedEdge(0, 1);
		mg.makeUndirectedEdge(0, 2);
		mg.makeUndirectedEdge(0, 3);
		mg.makeUndirectedEdge(1, 4);
		mg.makeUndirectedEdge(1, 5);
		mg.makeUndirectedEdge(2, 6);
		mg.makeUndirectedEdge(3, 6);
		mg.makeUndirectedEdge(3, 7);
		mg.bfs(0);
	}
}