[바미] Search algorithm - Depth-first search 구현하기

DFS(깊이 우선 탐색)은 그래프 탐색 알고리즘 중 하나로, 루트 노드(시작 노드)에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다. 즉, 가능한 한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 루트로 탐색하는 방법입니다.

 

function DFS(graph, start) {
  const visited = {};
  for (let i = 0; i < graph.length; i++) {
    visited[i] = false;
  }
  DFSUtil(start, visited, graph);
}

function DFSUtil(vertex, visited, graph) {
  visited[vertex] = true;
  console.log(vertex);
  const neighbors = graph[vertex];
  for (let i = 0; i < neighbors.length; i++) {
    const neighbor = neighbors[i];
    if (!visited[neighbor]) {
      DFSUtil(neighbor, visited, graph);
    }
  }
}

위 코드는 그래프를 표현하는 인접 행렬과 시작 노드를 인자로 받아 DFS 알고리즘을 실행합니다.

 

먼저, visited 객체를 선언하고 초기값을 false로 설정합니다.

이 객체는 노드가 방문되었는지 여부를 나타내며, visited[i]는 노드 i가 방문되었는지 여부를 나타냅니다.

 

그리고 DFSUtil 함수를 호출합니다. 이 함수는 vertex(현재 노드), visited(방문한 노드 목록), graph(그래프)를 인자로 받습니다.

 

DFSUtil 함수에서는 visited[vertex]를 true로 설정하고, 현재 노드를 출력합니다. 그리고 vertex의 모든 이웃 노드를 탐색합니다. 이웃 노드 neighbor가 방문되지 않았다면, DFSUtil(neighbor, visited, graph)를 호출합니다. 이렇게 함으로써 깊이 우선으로 노드를 탐색할 수 있습니다.

 

마지막으로 DFS 함수를 호출하면, 시작 노드에서부터 DFS 알고리즘을 실행합니다.

위와 같이 구현된 DFS 알고리즘은 그래프의 탐색, 미로 찾기 등에 이용됩니다.