그래프 탐색 (BFS, DFS)

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

• 모든 정점을 발견하는 가장 단순하고 고전적인 방법이다.

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

• DFS 하나에 for loop을 N번을 탐색하기 때문에 O(N) , 정점을 방문할 때 마다 DFS를 부르는데, N개의 정점을 모두 방문하므로 O(N) 이다. 따라서 인접행렬 DFS의 전체 시간복잡도 = N * O(N) = O(N^2) 이다

깊이 우선 탐색은 탐색의 각 과정에서 가능한 한 그래프 안으로 깊이 들어가려고 시도하며, 막힌 정점에 도달하지 않는 한 뒤로 돌아가지 않는다.

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

• 다익스트라, 프림 알고리즘은 BFS를 근간으로 이루어진 알고리즘이다.
• DFS에 비해 동작 과정은 비교적 이해하기 쉽다.

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

• 따라서 너비 우선 탐색의 방문 순서는 정점의 목록에서 어떤 정점을 먼저 꺼내는지에 의해 결정된다.

모든 정점은 세가지 상태를 거치게 된다.

1. 아직 발견되지 않은 상태 (!check[i])
2. 발견되었지만 방문하지 않은 상태
3. 방문된 상태 (check[i])

BFS / DFS 언제 어느 것을 사용해야하나?

각각의 장단점이 있으므로 문제의 유형을 잘 파악하고 그에 적합한 방식을 대입하는 것이 중요하다

• 모든 노드를 방문하고자 하는 경우에 DFS를 선택함
• 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함
• 검색 속도 자체는 너비 우선 탐색(BFS)이 더 빠름

따라서

• 검색 대상 그래프가 정말 크다면 DFS (깊이우선)
• 검색 대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS (너비우선)을 선택하자.

---

| 탐색 과정 예시