그래프 탐색 DFS

이 글에서는 DFS에 대해 알아보겠습니다.

---

그래프 탐색이란?

이전글에서 다뤘던 내용이지만 다시 설명하자면

 

그래프에서 각 정점들을 중복 없이 한 번씩 방문하는 방법입니다.

 

종류는 두 가지 종류가 있고 그 중 하나인 너비 우선 탐색(BFS)은 저번글에서 다뤘고 이제 남은 하나인 깊이 우선 탐색(DFS)를 알아보도록 합시다. 

---

깊이 우선 탐색

깊이 우선 탐색은 한 방향으로 갈 수 있는 만큼 가다가 더 이상 갈 수 없을 때 가장 가까운 갈림길로 돌아와서 다시 탐색을 진행하는 순회 방법입니다.

 

이 역시 말만 들으면 이해가 힘드니 그림을 봅시다.

위의 그림이 있다고 했을때 시작은 당연히 루트(근노드)이니 루트를 첫 번째로 방문합니다.

 

이제 탐색을 본격적으로 해봅시다.

우선 한방향으로 나아가기 위해 Level1 3개의 노드 중 하나로 가야 합니다. 이전글에서도 이야기했다시피 이럴 때는 왼쪽부터 갑니다. 그러니 Level1의 왼쪽노드를 두번째로 방문합니다.

 

다음은 어디일까요?

 

DFS의 정의에서 한 방향으로 갈 수 있는만큼 간다고 하였습니다. 그럼 간선으로 연결된 노드가 있나 확인합니다.

확인해 보면 하나의 노드가 연결되어 있는 것을 볼 수 있습니다. 그럼 거기로 가면 되죠. Level2의 왼쪽 노드가 3번째로 방문된 노드가 됩니다.

 

이제 다음은 더 이상 연견된 노드가없으니 Level1의 중간노드로 옵니다(4번째 방문).

Level1의 중간노드와 연결된 노드가 2개이니 왼쪽을 5번째로 방문합니다.

다시 한 번 연결된 노드가 있나 확인합니다. 하나의 노드가 연결되어 있으니 방문합니다(6번째).

 

이제 확인해보면 연결된 노드가 없습니다. 그러면 돌아가야죠.

정의를 보면 가장 가까운 갈림길로 돌아간다고 하였으니 Level1의 중간노드를 다시 확인합니다.

이제 아직 방문하지 않았던 하나의 노드를 방문합니다. 이러한 방법으로 계속 탐색을 하다 보면 아래 그림과 같이 탐색이 완료될 것입니다.

숫자가 방문순서입니다.

깊이 우선 탐색이라는 이름처럼 깊게 탐색하는 게 특징이라 볼 수 있습니다.

---

마무리

이번글은 여기까지입니다. 도움이 되셨다면 좋겠네요.

혹시나 피드백할 점이 있거나 잘못된 정보가 있다면 댓글로 적어주세요. 피드백은 모르겠지만 잘못된 정보는 큰일 날 수도 있습니다. 진짜로...