[알고리즘] BFS(너비 우선 탐색), DFS(깊이 우선 탐색) 비교

너비 우선 탐색은 가까운 것 위주로 탐색합니다.

최단경로를 찾아줍니다.

미로 찾기에서 많이 사용됩니다.

너비 우선 탐색을 구현하기 위해서는 fist in first out 자료구조인 큐를 사용해 구현할 수 있습니다.

예시를 통해 함께 살펴보죠.

 

큐에 노드 1을 넣어줍니다. [1]

1을 방문 처리해줍니다.

큐에서 1을 꺼냅니다. []

1과 연결된 노드 중 방문하지 않은 2,3을 큐에 넣어줍니다. [2,3]

큐에서 2를 꺼냅니다. [3]

2와 연결된 노드 중 방문하지 않은 4,5를 큐에 넣어줍니다. [3,4,5]

큐에서 3을 꺼냅니다. [4,5]

3과 연결된 노드 중 방문하지 않은 6,7을 큐에 넣어줍니다. [4,5,6,7]

큐에서 4를 꺼냅니다. [5,6,7]

4와 연결된 노드 중 방문하지 않은 노드가 없습니다. [5,6,7]

5,6,7 또한 마찬가지입니다.

이제 큐에서 순서대로 꺼내 주시면 됩니다.

방문 순서는 1,2,3,4,5,6,7입니다.

거리가 가까운 것부터 방문합니다.

 

깊이 우선 탐색과 비교해보도록 하겠습니다.

 

깊이 우선 탐색은 first in last out 자료구조인 스택을 사용합니다.

1을 스택에 넣어줍니다. [1]

1과 가장 가까운 노드 중 가장 작은 2를 스택에 넣어줍니다. [2,1]

2과 가장 가까운 노드 중 가장 작은 3을 스택에 넣어줍니다. [3,2,1]

3과 가장 가까운 노드 중 가장 작은 6을 스택에 넣어줍니다. [6,3,2,1]

6과 가장 가까운 노드 중 가장 작은 7을 스택에 넣어줍니다. [7,6,3,2,1]

7은 방문하지 않은 인접 노드가 없습니다.

이때는 스택에서 하나씩 꺼내면 됩니다.

6,3도 마찬가지이기 때문에 꺼냅니다. [2,1]

2와 가장 가까운 노드 중 가장 작은 4를 스택에 넣어줍니다. [4,2,1]

4와 가장 가까운 노드 중 가장 작은 5를 스택에 넣어줍니다. [5,4,2,1]입니다.

이제 5,4,2,1은 방문하지 않은 이웃 노드가 없기 때문에 순서대로 나옵니다.

1,2,3,6,7,4,5 순서로 방문하게 됩니다.

가까운 곳부터 살피는 것이 아니라 깊게 살핍니다.