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

DFS

DFS (Depth-First Search)는 그래프와 트리 구조에서 사용되는 탐색 알고리즘 중 하나로, 특정 노드에서 시작하여 깊이를 우선으로 탐색하는 방법입니다. DFS는 스택(Stack) 또는 재귀 함수를 사용하여 구현할 수 있으며, 그래프 또는 트리의 모든 노드를 방문하거나 특정 조건을 만족하는 노드를 찾을 때 유용하게 사용됩니다.

 

DFS 알고리즘의 동작 원리

1. 시작 노드를 방문하고, 방문한 노드를 스택(Stack)에 저장하거나 현재 함수의 호출 스택에 넣습니다.
   
   
2. 현재 노드와 연결된 이웃 노드 중에서 방문하지 않은 노드를 선택합니다. 이때, 어떤 이웃 노드를 선택하느냐에 따라 "깊이 우선"이 결정됩니다.
   
   
3. 선택한 이웃 노드로 이동하여 다시 스택에 저장하거나 재귀 호출합니다.
   
   
4. 이동한 노드에서 다시 방문하지 않은 이웃 노드를 선택하고 같은 과정을 반복합니다.
   
   
5. 스택이 비어있거나 재귀 호출이 종료될 때까지 위 과정을 반복하여 그래프 또는 트리를 탐색합니다.

DFS의 특징

스택 또는 재귀 호출을 사용하므로, 깊이를 우선으로 탐색하며 현재 경로를 완전히 탐색합니다.
모든 노드를 방문하거나 특정 조건을 만족하는 노드를 찾을 때까지 진행합니다.
특정 경로를 따라 탐색할 때 유용하며, 그래프에서 사이클을 찾거나 노드 간의 경로를 확인하는 데 사용됩니다.
DFS는 그래프 알고리즘, 미로 찾기, 토폴로지 정렬, 컴퓨터 네트워크 라우팅 등 다양한 응용 분야에서 사용됩니다. 이 알고리즘을 이해하면 그래프와 트리 구조를 탐색하고 문제를 해결하는 데 유용한 기술을 배울 수 있습니다.

 

 

그래프로 DFS사용 예시

class Graph {
  constructor() {
    this.adjacencyList = new Map();
  }

  addVertex(vertex) {
    // 새로운 노드를 추가할 때 빈 배열로 초기화
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  addEdge(v1, v2) {
    // 두 노드 사이에 연결선(간선) 추가
    this.adjacencyList.get(v1).push(v2);
    this.adjacencyList.get(v2).push(v1);
  }

  dfs(startingNode) {
    const visited = new Set(); // 방문한 노드를 저장하기 위한 Set

    // 내부 함수를 정의하여 재귀적으로 DFS 실행
    function explore(node) {
      if (!node || visited.has(node)) return;

      // 현재 노드 방문 처리
      visited.add(node);
      console.log(node);

      // 현재 노드와 연결된 모든 이웃 노드를 탐색
      const neighbors = this.adjacencyList.get(node);
      for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
          explore.call(this, neighbor);
        }
      }
    }

    explore.call(this, startingNode);
  }
}

// 예시 그래프 생성
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("B", "E");

// DFS 실행 (시작 노드: "A")
console.log("DFS traversal starting from A:");
graph.dfs("A");