Chapter 14. 그래프의 탐색

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

그래프의 탐색은 그 어떤 자료구조보다도 복잡한 편입니다. 그래프는 정점의 구성뿐만 아니라 간선의 연결에도 규칙이 존재하지 않기 때문입니다. 그래서 그래프의 탐색을 위한, 다시 말해서 그래프의 모든 정점을 돌아다니기 위한 별도의 알고리즘 두 가지를 소개합니다.

• 깊이 우선 탐색    Depgh First Search(DFS)
• 너비 우선 탐색    Breadgh First Search(BFS)

 

우선은 깁이 우선 탐색의 방법을 먼저 설명하겠습니다. 아래의 그래프는 앞서 보였던 비상 연락망입니다.

현재 L 학생에게 비상 메시지가 전달되었습니다. 따라서 L 학생을 시작으로 모든 학생들에게 비상 메시지가 전달되어야 합니다. L 학생은 K 학생과 M 학생에게 연락할 수 있지만, 우선 둘 중 어느 한 사람에게 메시지를 보내면 메시지가 돌고 돌아 결국 K 학생에게까지 전달될 것이라고 생각하고 M 학생에게만 메시지를 전달했습니다. 그리고 다른 모든 학생들도 똑같은 생각으로 한 학생에게만 연락을 취한다고 가정해 보겠습니다.

 

비상 메시지는 L 학생을 시작으로 M 학생, N 학생, J 학생에게 순서대로 전달되었습니다.

그리고 J 학생은 N 학생과 I 학생에게 연락할 수 있으나 N 학생으로부터 연락을 받았기 때문에 I 학생에게 연락합니다.

I 학생은 J 학생으로부터 연락을 받았고, N 학생은 이미 비상 메시지를 전달받았습니다. 따라서 I 학생은 비상 메시지를 전달할 곳이 없습니다. 그래서 자신에게 연락을 해 온 학생에게 다음과 같이 연락합니다.

 

"내가 연락할 수 있는 학생들은 모두 비상 메시지를 받았어, 혹시 네가 연락해야 할 학생들 중에 연락을 아직 못 받은 학생이 있으면 그 학생에게 연락해"

 

그런데 이는 J 학생도 마찬가지이므로 똑같이 N 학생에게 전달합니다. 그리고 N 학생은 자기가 연락할 수 있는 학생들 중 아직 K 학생이 연락을 못 받았음을 알고 비상 메시지를 전달합니다.

이로써 모든 학생들이 비상 메시지를 전달받게 되었습니다. 하지만 여기서 끝나지는 않습니다. 완전한 탐색이 이뤄졌다고 말할 수 있으려면 처음 비상 메시지를 전달했던 L 학생에게 다시 회신이 와야 합니다. K 학생이 N 학생으로부터 연락을 받았고, 더 연락할 곳이 없으므로 N 학생에게 

 

"내가 연락할 수 있는 학생들은 모두 비상 메시지를 받았어, 혹시 네가 연락해야 할 학생들 중에 연락을 아직 못 받은 학생이 있으면 그 학생에게 연락해"

 

하고 전달합니다. 그리고 N 학생은 M 학생에게, M 학생은 L 학생에게 똑같이 전달합니다. 이렇게 해서 L 학생에게까지 회신이 닿았고, 이로써 그래프의 완전한 탐색이 이뤄졌습니다.

 

지금까지 설명한 DFS의 핵심 세 가지를 비상 연락망에 빗대어 정리하면 다음과 같습니다.

• 한 사람에게만 연락한다.
• 연락할 사람이 없으면, 자신에게 연락한 사람에게 이를 알린다.
• 처음 연락을 시작한 사람의 위치에서 연락은 끝이 난다.