BFS(왼쪽)와 DFS(오른쪽)

BFS(Breadth-First Search / 너비 우선 탐색)

• 시작정점에서부터 인접해 있는 노드를 우선으로 탐색하는 방법
• 두 개의 큐를 사용
• 주로 최단거리를 구하는 문제에 사용

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 bfs = (graph, start) => {
  let visited = [];  // 탐색 마친 노드
  let needVisit = []; // 탐색해야할 노드(queue)
  
  needVisit.push(start);  // 시작노드
  
  // 탐색해야 하는 노드가 아직 남아있다면
  while(needVisit.length !== 0){
    let node = needVisit.shift();  // queue는 선입선출(shift)
    if(!visited.includes(node)){  // node가 탐색 마친 노드 아니라면
      visited.push(node);
      needVist = [...needVisit, ...graph[node]]; // 기존의 (needVisit + node의 자식들) 큐에 삽입
    }
  }
  return visited;
}

DFS(Depth-First Search / 깊이 우선 탐색)

• 시작정점에서부터 해당 분기를 전부 탐색 한 후 다음 분기를 탐색하는 방법
• 한개의 큐, 한개의 스택을 사용
• 주로 경로의 존재 여부를 판별하는 문제에 사용

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, start) => {
  let visited = [];  // 탐색 마친 노드
  let needVisit = []; // 탐색해야할 노드(stack)
  
  needVisit.push(start);  // 시작노드
  
  // 탐색해야 하는 노드가 아직 남아있다면
  while(needVisit.length !== 0){
    let node = needVisit.pop();  // stack은 선입후출(pop)
    if(!visited.includes(node)){  // node가 탐색 마친 노드 아니라면
      visited.push(node);
      needVist = [...needVisit, ...graph[node]]; // 기존의 (needVisit + node의 자식들) 큐에 삽입
    }
  }
  return visited;
}

참고사이트

• https://velog.io/@jminkyoung/AL-BFS-DFS-JavaScript