Java - DFS 구현

 1. DFS

 DFS(Depth-first Search)을 직역하면 깊이 우선 탐색이라는 뜻으로, 연결된 노드를 따라 방문을 한 뒤에 더 이상 연결된 노드가 없을 때 이전 노드로 돌아가서, 이전 노드에 연결된 노드를 따라 탐색하는 법입니다.

 

 위의 사진에서 1번 노드부터 탐색을 한다고 해보겠습니다. 오름차순으로 방문한다는 가정하에 1 -> 2 -> 6 순으로 진행됩니다. 6과 연결된 노드가 없기 때문에 다시 2번 노드로 돌아가 8번 노드를 방문하게 됩니다. 8번 노드와 인접한 노드는 모두 방문을 끝냈기 때문에 최상위 노드(1번)으로 돌아가 3번 노드부터 시작하여 마찬가지로 오름차순으로 진행하여 3번 노드부터 이어진 노드를 방문합니다.

 위의 과정을 거치고나면 1 -> 2 -> 6 -> 8 -> 3 -> 5-> 4-> 7의 순서가 나오게 됩니다. 이러한 DFS 방식을 표현하는 방법에는 재귀함수(Recursion)를 이용한 것과 Stack이라는 자료구조를 이용한 방법이 있습니다. 코드를 통해 한번 살펴보겠습니다.

 

---

 2. 재귀(Recursion)를 이용한 구현

 먼저 graph에 2차원 배열의 형식으로 각 노드가 연결된 상태를 알려주도록 합니다. 첫 번째 0번 index는 비워두고, 노드가 1번부터 시작하기 때문에 1번 노드와 연결된 2, 3, 8번 노드를 표기하는 식입니다. 그 이후 index별 번호가 다음 노드와 연결되어 있다는 것을 표시해놨습니다. 이후 visited를 boolean으로 이미 노드에 방문한 것이라면 true를 반환하도록 했습니다. 시작점은 1이기 때문에 dfs(1)을 호출하게 되면 visited[1] = true;가 되고 이어서 메서드를 계속 진행하게 됩니다.

 조건문으로 노드가 방문을 안했다면 dfs를 통해 재귀함수를 실행하도록 하고, 조건문에서 2번 노드가 방문을 하지 않았기 때문에 nodse의 인자로 2를 대입하게 되면서 재귀함수를 반복하게 됩니다.

 

 결과는 위의 그림에서의 과정과 동일하게 출력이 되는 것을 볼 수가 있었습니다.

---

 

 3. Stack 자료구조를 이용한 구현

 다음은 Stack을 이용한 구현 방법입니다. 

처음에 1번 노드를 Stack에 넣어준 뒤, Stack이 비어있지 않을 때까지 반복하는 조건문을 선언합니다. Stack에서 꺼낸 노드가 인접한 노드와 Stack에서 꺼낸 노드가 인접하는지 확인한 뒤 방문하지 않았을 때 Stack에 다시 넣고 방문한 것으로 처리하는 과정입니다. 

 결과는 다음과 같습니다.