[Algorithm] DFS와 BFS의 쉬운 개념 + JavaScript 구현 방법

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

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

참고사이트

그래프 알고리즘으로, 문제를 풀 때 상당히 많이 사용함

경로를 찾는 문제 시, 상황에 맞게 DFS와 BFS를 활용하게 된다.

DFS(Depth First Search)

설명

루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기전에, 해당 브랜치를 모두 탐색하는 방법

• 스택 or 재귀함수를 통해 구현함
• 모든 경로를 방문해야 할 경우 사용에 적합하다

시간 복잡도

• 인접 행렬 : O(V^2)
• 인접 리스트 : O(V + E)
• V는 접점, E는 간선을 뜻함

코드

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"]
};

const DFS = (graph, startNode) => {
  const visited = []; // 탐색을 마친 노드들
  let needVisit = []; // 탐색해야할 노드들

  needVisit.push(startNode); // 노드 탐색 시작

  while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
    const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
    if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면
      visited.push(node); 
      needVisit = [...graph[node], ...needVisit];
    }
  }
  return visited;
};

console.log(DFS(graph, "A"));
// ["A", "B", "D", "E", "F", "C", "G", "H", "I", "J"]

BFS(Breadth First Search)