[Graph] DFS와 BFS

DFS?

Depth First Search의 약자이다. 즉, 깊이우선 탐색 알고리즘이다.

그렇다면 DFS 알고리즘은 어떻게 동작하는 지 알아보자.

 

---

IDEA

Graph

위와 같이 생긴 그래프를 노드 0에서부터 깊이 탐색을 해보자.

 

1.

0번 노드 탐색

0   

2.

1번 노드 탐색

0 -> 1 

3.

5번 노드 탐색

0 -> 1 -> 5 

5번 노드에서 갈 수 있는 노드가 없으므로 다시 뒤로 복귀한다.

4.

5번노드에서 1번노드로 복귀

1번 노드에서 0번 노드로 복귀

0 -> 1 -> 5 

1번 노드 또한 더 이상 탐색할 수 있는 노드가 없으므로 0번으로 복귀한다.

5.

2번 노드 탐색

0 -> 1 -> 5 -> 2

0번에서 2번을 탐색할 수 있으므로 2번을 탐색한다.

6.

 

3번 노드 탐색

0 -> 1 -> 5 -> 2 -> 3

6.

6번 노드 탐색

0 -> 1 -> 5 -> 2 -> 3 -> 6

7.

7번 노드 탐색

0 -> 1 -> 5 -> 2 -> 3 -> 6 -> 7

7번 노드에서 0번으로 갈 수 있지만, 0번 노드는 이미 방문한 노드이므로 탐색을 새로 하지 않는다.

따라서 다시 탐색할 것이 남아있는 노드로 복귀한다.

8.

7번 노드에서 6번 노드로 복귀

6번 노드에서 3번 노드로 복귀

3번 노드에서 2번 노드로 복귀

2번 노드에서 0번 노드로 복귀

0 -> 1 -> 5 -> 2 -> 3 -> 6 -> 7 -> 4

3번노드에서 5번노드로 갈수 있지만, 이미 5번노드를 탐색했으므로 2번 노드로 복귀한다. 그리고 탐색할 수 있는 노드까지 복귀하면, 0번 노드에서 4번 노드로 갈 수 있다.

9.

4번 노드 탐색

4번 노드에서 5번 노드로 갈 수 있지만, 이미 탐색을 마친 노드이므로 탐색을 할 수 없다.

더 이상 탐색할 수 있는 노드가 없으므로 DFS탐색을 마무리한다.

 

이제, 위에서 알아본 DFS의 원리를 토대로 코드를 작성해보자.

---

CODE

DFS 코드

 

 

---

BFS?

Breadth First Search의 약자이다. 즉, 넓이우선 탐색 알고리즘이다.

그렇다면 BFS 알고리즘은 어떻게 동작하는 지 알아보자.

 

---

IDEA

위에 사용했던 그래프를 사용하여 BFS 탐색을 해보자.

1.

깊이 0 탐색

0 

노드 0을 깊이 0으로 노드 0과 연결된 노드들을 탐색한다.

 

2.

깊이 1 탐색

0 -> 1, 2, 3, 4

노드 0과 연결된 노드 1, 2, 3, 4 노드와 연결된 노드들을 탐색한다.

 

3.

깊이 2 탐색

 

 

깊이 3 탐색

0 -> 1, 2, 3, 4 -> 5, 6 -> 7

노드 5, 6과 연결된 노드 7과 연결된 노드가 노드 0이다. 하지만 노드 0의 경우 이미 탐색을 완료한 노드이므로 탐색을 마친다.

 

이제 위에서 탐색한 BFS 알고리즘에 대해 코드를 구현해 보자.

 

---

CODE

BFS 코드