[코쿼 알고리즘 스터디 with 케이시] BFS, DFS

BFS

Breadth - First - Search
너비 우선 탐색이다.

최단 거리를 구하는 알고리즘에서 사용이 된다.

DFS

Depth - First - Search
깊이 우선 탐색

마찬 가지로 최단 거리를 구하는 알고리즘에서 사용된다.

사용처

• 최단 거리를 구하는 알고리즘
• 그림판 알고리즘

D에서 G로 가는 최단거리는?

그래프 탐색 알고리즘

• 너비 우선 탐색
• 깊이 우선 탐색

너비 우선 탐색

• 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘
  • 정점, A,B,C 등 기준점

큐를 이용해 탐색한 정보를 관리

1. D를 먼저 탐색 -> D를 엔큐
2. 이어서 같은 거리에 있는 E, A 등을 탐색 -> E, A를 엔큐
3. D를 디큐,
4. E를 디큐하고 E에서 갈 수 있는 정점이 없으므로 엔큐는 하지 않는다.
5. A에서 갈 수 있는 B와 C를 엔큐, 그리고 A를 디큐
6. B에선 F로 갈 수 있으므로 F를 엔큐, A는 한번 거친 길이므로 엔큐하지 않는다.
7. B를 디큐
8. C를 디큐, C에선 다 가본 정점뿐이 없으므로 엔큐하지 않는다.
9. G를 엔큐, F 를 디큐, 최종적으로 G를 디큐

정리하면, 시작점을 엔큐하고, 시작점에서 갈 수 있는 정점을 엔큐하고, 시작점을 디큐한다.

큐의 가장 앞에 있는 정점에서, 갈 수 있는 정점을 엔큐하고, (없으면 하지 않고) 가장 앞 큐를 디큐한다. 

그 다음 가장 앞에 있는 큐에서 갈 수 있는 정점을 엔큐하고, 그 다음 가장 앞 큐를 디큐한다. 

반복 ~ 참고로 Queue는 First In First Out 의 구조이다.

BFS 특징

• Queue 를 이용하여 구현할 수 있다.
• 시작 지점에서 가까운 정점부터 탐색한다.
• V가 정점의 수, E가 간선의 수일 때, BFS의 시간복잡도는 O(V + E)다.

깊이 우선 탐색

그래프 탐색 알고리즘으로 최대한 깊은 정점부터 탐색하는 알고리즘

DFS 특징

• 스택을 이용하여 구현할 수 있다.
• 시작 정점에서 깊은 것 부터 찾는다.
• V가 정점의 수, E가 간선의 수 일 때 BFS의 시간 복잡도는 O(V + E) 다.

 

1. A를 스택에 푸쉬한다. 

2. A에서 갈 수 있는 B를 푸쉬한다. 

3. B에서 갈 수 있는 F를 푸쉬한다. 

4. F에서 갈 수 있는 C를 푸쉬한다. 

5. C에선 더 갈 정점이 없으므로 TOP 인 C를 팝한다.

6. 다시 F에서 갈 수 있는 G를 푸쉬한다. 

7. 더 이상 갈 정점이 없으므로, B,F,G 정점을 팝한다. 

8. A에서 갈 수 있는 D 를 푸쉬한다. 

9. D에서 갈 수 있는 E를 푸쉬한다. 

10. 더 이상 갈 곳이 없으므로, A, D, F를 팝한다. 

참고로, Stack 은 Last In First Out 의 구조이다. 

요약하자면, 시작점을 푸쉬한다.  A

그 한 지류를 갈 수 있는 끝까지 가는 모양새다.

 

BFS 는 파문형으로 넓어져 나가며, DFS 는 가로질러서 탐색한다.