DFS(깊이 우선 탐색)는 형제(sibling) 정점보다 자식(child) 정점을 먼저 방문하는 알고리즘입니다. 즉, 너비를 넓히며 탐색하기 전에 특정 경로의 깊이를 끝까지 따라 내려가는 방식으로 그래프를 순회합니다. DFS를 구현할 때는 일반적으로 스택(Stack)을 사용하며, 재귀 호출 시 프로그램의 콜 스택(call stack)이 이 역할을 대신 수행하기도 합니다.
DFS의 동작 원리
DFS는 다음과 같은 규칙에 따라 동작합니다.
- 인접한 방문하지 않은 정점을 방문하고, 방문 처리한 뒤 화면에 표시하고 스택에 push합니다.
- 방문하지 않은 인접 정점이 없다면, 스택에서 정점을 하나 pop합니다. (인접 정점이 없는 정점들은 모두 스택에서 빠져나오게 됩니다.)
- 스택이 빌 때까지 규칙 1과 규칙 2를 반복합니다.
DFS 순회 과정 단계별 살펴보기
아래 표는 실제 그래프에서 DFS 순회가 진행되는 과정을 단계별로 보여줍니다.
| 단계 | 순회 과정 | 설명 |
|---|---|---|
| 1 |  | 스택을 초기화합니다. |
| 2 |  | S를 방문 처리하고 스택에 넣습니다. S의 인접 노드 중 방문하지 않은 노드를 탐색합니다. 후보 노드가 세 개 있으며, 이 예제에서는 알파벳 순서대로 선택합니다. |
| 3 |  | A를 방문 처리하고 스택에 넣습니다. A의 인접 노드를 탐색하는데, S와 D가 인접해 있지만 여기서는 방문하지 않은 노드만 고려합니다. |
| 4 |  | D를 방문하고 방문 처리한 뒤 스택에 넣습니다. D에는 B와 C라는 두 개의 인접 노드가 있고 모두 아직 방문하지 않았습니다. 마찬가지로 알파벳 순서를 따라 선택합니다. |
| 5 |  | B를 선택하여 방문 처리하고 스택에 넣습니다. B에는 더 이상 방문하지 않은 인접 노드가 없으므로 B를 스택에서 pop합니다. |
| 6 |  | 스택의 최상단을 확인하여 이전 노드로 되돌아간 뒤, 해당 노드에 방문하지 않은 노드가 있는지 확인합니다. 여기서는 D가 스택의 맨 위에 있습니다. |
| 7 |  | D의 인접 노드 중 유일하게 방문하지 않은 노드는 C입니다. C를 방문하고 방문 처리한 뒤 스택에 넣습니다. |
C에도 방문하지 않은 인접 노드가 없으므로, 방문하지 않은 인접 노드를 가진 노드를 찾을 때까지 계속해서 스택에서 pop합니다. 이 예제에서는 그런 노드가 없으므로 스택이 완전히 비워질 때까지 pop을 반복하게 됩니다.
자바스크립트로 DFS 구현하기
그럼 이 알고리즘을 자바스크립트로 어떻게 구현할 수 있는지 살펴보겠습니다.
예제 코드
DFS(node) {
// 스택을 생성하고 시작 노드를 추가합니다.
let s = new Stack(this.nodes.length);
let explored = new Set();
s.push(node);
// 첫 번째 노드를 방문(explored) 처리합니다.
explored.add(node);
// 스택이 빌 때까지 반복합니다.
while (!s.isEmpty()) {
let t = s.pop();
// 스택에서 꺼낸 요소를 콘솔에 출력합니다.
console.log(t);
// 1. edges 객체에서 현재 노드와 직접 연결된 노드들을 찾습니다.
// 2. 이미 탐색된 노드는 필터링으로 제외합니다.
// 3. 아직 탐색하지 않은 노드를 explored로 표시하고 스택에 push합니다.
this.edges[t]
.filter(n => !explored.has(n))
.forEach(n => {
explored.add(n);
s.push(n);
});
}
}생각보다 간단하지 않나요? 핵심은 큐(Queue)를 스택(Stack)으로 교체한 것뿐입니다. 바로 이 차이만으로 BFS가 DFS가 됩니다. 사실 이것이 두 알고리즘 구현상의 거의 유일한 차이점입니다.
물론 DFS는 재귀(recursion)로도 구현할 수 있습니다. 하지만 이 경우 재귀 구현은 피하는 것이 좋습니다. 그래프가 커질수록 콜 스택을 추적하기 위해 추가 메모리가 필요해지기 때문입니다.
테스트 코드
아래 코드로 직접 구현한 DFS를 테스트해볼 수 있습니다.
let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");
g.addEdge("A", "C");
g.addEdge("A", "B");
g.addEdge("A", "D");
g.addEdge("D", "E");
g.addEdge("E", "F");
g.addEdge("B", "G");
g.DFS("A");실행 결과
위 코드를 실행하면 다음과 같은 출력 결과를 얻습니다.
A D E F B G C
출력 결과를 보면 시작 노드 A에서 출발해 D → E → F 경로를 끝까지 깊게 탐색한 후, 다시 돌아와 B → G 경로를 탐색하고 마지막으로 C를 방문하는 것을 확인할 수 있습니다. 이것이 바로 DFS의 핵심 특징인 '깊이 우선' 순회 방식입니다.