[Algorithm] 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) - 그래프 탐색 알고리즘

이 글은 그래프 탐색 알고리즘의 대표적인 알고리즘, 깊이 우선 탐색(DFS) 알고리즘과 너비 우선 탐색(BFS) 알고리즘을 소개한다.

그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘들을 그래프의 탐색 알고리즘이라고 한다. 탐색 알고리즘 중 가장 널리 사용되는 두 가지는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이다. 

 

깊이 우선 탐색(DFS: Depth First Search)

깊이 우선 탐색은 현재 정점과 인접한 정점들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 따라간다. 이 과정에서 더이상 갈 곳이 없는 막힌 정점에 도달하면 마지막에 따라왔던 간선을 따라 뒤로 돌아간다.

이는 재귀 호출을 이용하면 간단하게 구현할 수 있다.

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

너비 우선 탐색은 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘이다. 너비 우선 탐색은 각 정점을 방문할 때마다 모든 인접 정점을 검사한다. 이 중 처음 보는 정점을 발견하면 이 정점을 방문 예정이라고 기록해둔 뒤, 별도의 위치에 저장한다. 인접한 정점을 모두 검사하고 나면, 지금까지 저장한 목록에서 다음 정점을 꺼내서 방문하게 된다. 따라서 너비 우선 탐색의 방문 순서는 정점의 목록에서 어떤 정점을 먼저 꺼내는지에 의해 결정된다. 보통 큐(queue)에다 방문할 정점을 저장해 먼저 저장한 정점을 먼저 방문한다(first-in first-out).

차이

깊이 우선 탐색에서는 정점을 발견하자마자 해당 정점을 방문하지 않았으면 그 정점을 방문한다. 이와 달리 너비 우선 탐색에서는 발견과 방문이 같지 않다. 너비 우선 탐색에서 모든 정점은 다음과 같은 세 개의 상태를 순서대로 거쳐가게 된다.

1. 아직 발견되지 않은 상태

2. 발견되었지만 아직 방문되지는 않은 상태(방문할 정점의 목록은 큐에 저장되어 있다.)

3. 방문된 상태

예시

다음은 그래프를 각각 깊이 우선 탐색, 너비 우선 탐색 알고리즘으로 방문한 순서를 나타낸 예시이다.