DFS(Depth-First Search; 깊이우선탐색)

그래프 탐색(Graph Search)이란?

어떤 그래프에서, vertex s로부터 v까지의 path가 존재하는지 알아내는 것이다.

ex) 특정 도시에서 한 도시로 갈 수 있는가? / 나와 특정 사람 간에 페이스북 친구들을 매개로 이어질 수 있는가? 등

DFS(Depth-First Search; 깊이 우선 탐색)

미로 찾기

DFS에 대해 알아보기 전에, 여러 통행로(passage)와 교차로(intersection)들로 구성된 미로 속에서 길을 찾는 모습을 떠올려 보자. 미로에서 길 찾는 문제를 해결하는 방법으로 Tremaux exploration이라는 것이 있는데, 과정은 다음과 같다.

▪︎ 아직 방문하지 않은 통행로 중 아무 곳이나 가본다. 처음으로 지나가는 통행로에는 길을 따라 선을 그어 놓는다.

▪︎ 방문한 모든 교차로와 통행로에는 표시를 해 놓는다.

▪︎ 방문했던 교차로에 접근할 경우, 그어 놓은 선을 따라 되돌아간다.

▪︎ 되돌아 가는 과정에서, 방문하지 않은 교차로가 더 이상 남아 있지 않은 경우, 계속 단계를 되돌린다.

정리하면, 방문하지 않은 통행로가 있으면 앞으로 가고, 방문했던 통행로만 앞에 남아있는 경우에는 방문하지 않은 교차로가 나올 때까지 되돌아가는 것이다.

DFS

연결된 그래프에서, 탐색을 수행하는 전형적인 재귀 메소드는 위에서 살펴 본 미로 찾기 방법을 모방한 것이다. 즉 vertex들을 방문하는 재귀 메소드를 실행하는 것인데, 다음의 절차를 거친다.

▪︎ 방문하는 곳에는 표시를 해 놓는다.

▪︎ 현재 방문한 vertex와 인접하면서, 아직 방문하지 않은 vertex가 있다면 (재귀적으로) 방문한다.

이러한 방법을 우리는 Depth-First Search(DFS)라고 부른다. 

DFS를 구현하기 전에, Graph 클래스를 먼저 구현하였다.

DFS의 간단한 구현은 아래와 같다. 

DepthFirstSearch 클래스는 방문했는지의 여부를 기록하기 위한 boolean 배열(marked)을 가지며, 재귀 메소드인 dfs()가 주어진 vertex를 방문한 것으로 체크하고, 자신의 인접 리스트에 있으면서 아직 방문하지 않은 vertex에 대해 재귀적으로 메소드를 호출한다.

그런데 위의 DepthFirstSearch 클래스 내에 있는 dfs() 메소드는, 한 vertex에서 다른 vertex까지 가는데 필요한 path의 길이(count)는 구할 수 있지만, 어떤 vertex들을 거쳐서 전체의 path가 완성되는지는 알 수가 없는 상태다.

이번에는, 한 vertex(source)에서 다른 vertex까지의 path를 구하는 메소드(dfs())와, source로부터 특정 vertex까지의 path를 리턴하는 메소드(pathTo())까지 포함하는 DepthFirstPaths 클래스를 작성하였다.