깊이우선탐색(DFS)과 너비우선탐색(BFS)

위의 그림은 DFS와 BFS 경로를 순서대로 나타낸 것이다. 해당 그림을 통해 직관적으로 둘의 차이를 알 수 있을 것이다. 깊이 우선 탐색인 DFS는 가장 깊은 곳까지 방문하고 스택을 통해 구현한다.

너비우선탐색인 BFS는 같은 레벨 인접 노드를 전부 방문한 뒤 다음 레벨 인접 노드를 방문한다. 큐를 통해 구현한다.

 

 

---

깊이우선탐색 DFS

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

구현 방법

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

• 해당 그래프를 스택을 이용한다.
• 스택은 한 방향에서만 자료를 넣고 뺄 수 있는 후입선출 방식 구조이므로 가장 늦게 들오온 노드를 가장 먼저 뺄 수 있다.
• 또한 한 번 담았던 노드는 다시 담지 않는다.

1. 먼저 시작 노드인 0번 노드를 스택에 담았다.

2. 이후 0번 노드를 꺼내 출력하고 그 인접 노드인 1번 노드를 스택에 담았다. 

3. 이후 1번 노드를 꺼내 출력하고 그 인접 노드인 2번 노드와 3번 노드를 스택에 담았다.

4. 이후 3번 노드를 꺼내 출력하고 그 인접 노드인 4번 노드와 5번 노드를 스택에 담았다. 2번 노드는 이미 스택에 담겨있으므로 스택에 다시 추가하지 않는다.

5. 이후 5번 노드를 꺼내 출력하고 그 인접 노드인 6번 노드와 7번 노드를 스택에 담았다. 

6. 이후 7번 노드를 꺼내 출력하고 인접 노드가 없으므로 더 담지 않는다.

7. 이후 6번 노드를 꺼내 출력하고 그 인접 노드인 8번 노드를 스택에 담았다.

8. 이후 8번 노드를 꺼내 출력하고 인접 노드가 없으므로 더 담지 않는다.

9. 이후 4번 노드를 꺼내 출력하고, 2번 노드를 꺼내 출력한다, 더 꺼낼 노드가 없으므로 순회는 종료한다.

 

DFS 경로 : 0 > 1 > 3 > 5 > 7 > 6 > 8 > 4 > 2

출력 순서와 과정은 스택이기 때문에 위와 같이 이루어지는 것이다. 

 

---

 

너비우선탐색 BFS

그래프에서 가까운 노드부터 탐색하는 알고리즘이다.

구현방법

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

• 해당 그래프를 BFS로 구현해보자. 
• BFS는 Queue를 이용한다. 
• Queue는 가장 먼저 들어온 것이 가장 먼저 나가는 선입선출 방식의 구조이다. 
• DFS 구현과 마찬가지로 한번 큐에 담았던 노드는 다시 담지 않는다.

1. 먼저 시작 노드인 0번 노드를 큐에 담았다.

2. 이 후 0번 노드를 꺼내 출력하고, 그 인접 노드인 1번 노드를 큐에 담았다.

• 큐는 선입선출이므로 꺼내는 방향이 그림의 화살표처럼 아래부터이다.

3. 이 후 1번 노드를 꺼내 출력하고, 그 인접 노드인 2번 노드와 3번 노드를 큐에 담았다.

4. 이 후 2번 노드를 꺼내 출력하고, 그 인접 노드인 4번 노드를 큐에 담았다.
큐는 선입선출 방식이므로 가장 아래 있는 2번 노드부터 꺼낸다. 또한, 그 인접 노드 중 1번, 3번은 이미 큐에 들어갔었으므로 4번 노드만 큐에 담긴다.

5. 이 후 3번 노드를 꺼내 출력하고, 그 인접 노드인 5번 노드를 큐에 담았다.

6. 이 후 4번 노드를 꺼내 출력하고, 그 인접 노드는 전부 큐에 담았던 적이 있으므로 다시 담지 않는다.

7. 이 후 5번 노드를 꺼내 출력하고, 그 인접 노드인 6번 노드와 7번 노드를 큐에 담았다.

8. 이 후 6번 노드를 꺼내 출력하고, 그 인접 노드인 8번 노드를 큐에 담았다.

9. 이 후 7번 노드를 꺼내 출력하고, 8번 노드를 꺼내 출력한다. 더 꺼낼 노드가 없으므로 순회는 종료한다.

 

 

 

BFS 경로 : 0 > 1 > 2 > 3 > 4 > 5 > 6 > 7 > 8