[알고리즘] DFS 구현 - javascript

✅ DFS : 깊이우선탐색

• 트리 구조의 데이터에서 노드마다 가장 깊이까지 탐색한 뒤 다음 노드로 이동하는 방법
• 검색 속도는 BFS에 비해 느리지만 조금 더 간단
• 구현 방법
  1. 스택
  2. 재귀
  

✔️ 재귀

function dfs(graph, v, visited) {
  // 현재 노드 방문 처리
  visited[v] = true;
  console.log(v);
  
  // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for (let node of graph[v]) {
  	if (!visited[node]) {
    	dfs(graph, node, visited);
    }
  }
}

const graph = [[1, 2, 3], [0, 6], [0], [0, 4, 5], [3], [3], [1]];
const visited = Array(6).fill(false);

dfs(graph, 0, visited); // 0 1 6 2 3 4 5

✔️ 스택

function dfs(graph, start, visited) {
  const stack = []; // stack 정의
  stack.push(start);

  while (stack.length) {
    let v = stack.pop(); // stack의 최상위 값을 꺼내기
    if (!visited[v]) {
      // 방문하지 않았다면 방문처리
      console.log(v);
      visited[v] = 1;

      for (let node of graph[v]) {
        // 꺼낸 값의 자식 노드들을 방문
        if (!visited[node]) {
          // 방문하지 않은 노드라면 stack에 push
          stack.push(node);
        }
      }
    }
  }
}

const graph = [[1, 2, 3], [0, 6], [0], [0, 4, 5], [3], [3], [1]]; // 인접 리스트
const visited = Array(graph.length).fill(0); // 방문 여부 확인 리스트

dfs(graph, 0, visited);  // 0 3 5 4 2 1 6

• 재귀 dfs는 사전식 순서로 방문을 했지만, 스택 dfs는 역순으로 방문을 했다. 이것은 정상적으로 모든 노드의 방문을 마쳤기 때문에 잘못된 결과가 아니다!
• 자바스크립트는 스택을 이용한 dfs로 구현하는 것이 좋다.
• 현재 구현되어있는 스택 dfs 코드의 경우 stack이 끝나면 while문이 끝나기 때문에 마지막에 부모노드로 돌아가지는 않는다. 이 부분은 나중에 문제를 풀면서 만나게 되면 다시 정리해보고자 한다.

참고 블로그

[알고리즘] JavaScript로 구현하는 DFS