[바미] JS로 Depth-first

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 알고리즘을 실행합니다.

먼저 방문한 개체를 선언하고 초기 값을 false로 설정합니다.

이 객체는 노드를 방문했는지 여부를 나타내고,visit(i)는 노드 i를 방문했는지 여부를 나타냅니다.

그리고 DFSUtil 함수를 호출합니다. 이 함수는 Vertex(현재 노드), Visited(방문한 노드 목록) 및 Graph(그래프)를 인수로 사용합니다.

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

DFS 함수에 대한 최종 호출은 시작 노드에서 DFS 알고리즘을 실행합니다.

위와 같이 구현된 DFS 알고리즘은 그래프 검색 및 미로 찾기에 사용됩니다.