DFS 깊이 우선 탐색

DFS

DFS

• 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 자료 구조(or 재귀 함수)를 이용
  1) 탐색 시작 노드를 스택에 삽입하고 방문 처리
  2) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
  3) 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

DFS 동작 예시

1. 스택의 최상단 노드인 1에 방문하지 않은 인접 노드 2, 3, 8이 있다.
2. 이 중에서 가장 작은 노드인 2를 스택에 넣고 방문 처리를 한다.
3. 스택 최상단 노드인 2에 방문하지 않은 인접 노드 7이 있다.
   7번 노드를 스택에 넣고 방문 처리를 한다.
4. 스택의 최상단 노드인 7에 방문하지 않은 인접 노드 6 , 8이 있다.
5. 이 중 가장 작은 노드인 6을 스택에 넣고 방문 처리를 한다.
6. 스택의 최상단 노드인 6에 방문하지 않은 인접 노드가 없다.
7. 따라서 스택에서 6번 노드를 꺼낸다.
8. 스택의 최상단 노드인 7에 방문하지 않은 인접 노드 8이 있다.
9. 따라서 8번 노드를 스택에 넣고 방문처리를 한다.
10. 위와 같은 방법을 더이상 수행할 수 없을 때까지 반복한다.

JS DFS 알고리즘 구현

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "G", "H", "I"],
  D: ["B", "E", "F"],
  E: ["D"],
  F: ["D"],
  G: ["C"],
  H: ["C"],
  I: ["C", "J"],
  J: ["I"],
};

// (graph, 시작 정점)
const dfs = (graph, startNode) => {
  let needVisitStack = []; // 탐색을 해야 할 노드들
  let visitedQueue = []; // 탐색을 마친 노드들

  needVisitStack.push(startNode);

  // 탐색을 해야 할 노드가 남아 있다면
  while (needVisitStack.length !== 0) {
    const node = needVisitStack.pop();
    if (!visitedQueue.includes(node)) {
      visitedQueue.push(node);
      needVisitStack = [...needVisitStack, ...graph[node]];
    }
  }

  return visitedQueue;
};

console.log(dfs(graph, "A"));

// ["A", "C", "I", "J", "H", "G", "B", "D", "F", "E"]

참조)
https://ryusm.tistory.com/48