BFS / DFS

니나노개발생활·2021년 6월 21일

algorithm js

🔥algorithm https://github.com/skdud4659/TIL

목록 보기

9/16

그래프를 탐색하는 방법 BFS와 DFS

그래프란?

정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종

그래프 탐색 > 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

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

개념

정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식
(최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동하는 방식)

특징

두 개의 큐를 사용한다.
root와 가까운 노드부터 찾기 때문에 최단거리 탐색에 유용하다.
target이 root와 가까이 있다고 예상할 경우 사용한다.
큐를 이용하여 구현

사용 예시

지도 어플에서 특정 위치까지의 최단거리 안내
친구 추천
검색 대상의 규모가 크지 않고, 검색 시작 지점으로부터 대상이 멀지 않을 경우

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, startNode) => {
  let visited = []; // 탐색을 마친 노드들
  let needVisit = []; // 탐색해야할 노드들

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

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

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

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

개념

정점의 자식들을 먼저 탐색하는 방식
(최대한 깊이 내려간 뒤, 깊이 갈 곳이 없을 경우 옆으로 이동)

특징

한 개의 큐와 한 개의 스택을 사용한다.
루트 노드(또는 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색
BFS보다 간단하게 구현 가능하나 검색 속도 자체는 BFS에 비해 느림
재귀 또는 스택으로 구현

사용 예시

모든 노드를 방문하고자 하는 경우
미로 게임에서 경로가 존재하는지 판별할 때 유용
경로의 특징을 저장해야하는 경우 (a to b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안될 경우 등)
검색 대상 그래프가 아주아주 클 경우에 고려

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