[이론] BFS와 DFS (javascript)

💡 대표적인 트리 순회 알고리즘인 DFS와 BFS에 대해 알아보고, 자바스크립트로 구현해 봅시다.

BFS (넓이 우선 순회)

BFS란?

BFS는 Breadth-First-Search의 줄임말입니다.

트리를 순회할 때 같은 레벨의 노드(넓이)를 우선하여 순회하는 알고리즘을 의미합니다. 즉 현재 노드의 자식 노드보다 형제 노드를 우선하여 탐색합니다.

다음과 같은 트리 (그래프) 가 있을 때,

BFS를 이용한 순회 순서는 해당 그림과 같습니다.

BFS 구현 로직

BFS을 구현하기위한 로직은 다음과 같습니다.

1. 방문한 노드들을 기억할 배열을 생성해 줍니다.
2. 방문해야 하는 노드를 기억할 큐를 생성해 줍니다.
3. 방문해야하는 노드(= 큐의 길이)가 존재하는 한 큐에서 다음 방문할 노드를 뽑아 줍니다.
4. 뽑은 노드가 이미 방문했던 노드가 아니라면, 해당 노드의 자식 노드들을 큐에 후 순위로 넣어줍니다.
5. 방문해야 하는 노드가 없어질 때 까지 3-4 과정을 반복해줍니다.

자바스크립트로 DFS 구현하기

const BFS = (graph, firstNode) => {
  const visited = [];
  let needVisit = [];

  needVisit.push(firstNode);

  while (!!needVisit.length) {
    const node = needVisit.shift();
    if (!visited.includes(node)) {
      visited.push(node);
      needVisit = [...needVisit, ...graph[node]];
    }
  }

  return visited;
};

DFS (깊이 우선 순회)

DFS란?

DFS는 Depth-First-Search의 줄임말입니다.

트리를 순회할 때 깊이를 우선하여 순회하는 알고리즘을 의미합니다. 즉 현재 노드의 형제 노드보다 자식 노드를 우선하여 탐색합니다.

다음과 같은 트리 (그래프) 가 있을 때,

DFS를 이용한 순회 순서는 해당 그림과 같습니다.

DFS 구현 로직

DFS을 구현하기위한 로직은 다음과 같습니다.

1. 방문한 노드들을 기억할 배열을 생성해 줍니다.
2. 방문해야 하는 노드를 기억할 큐를 생성해 줍니다.
3. 방문해야하는 노드(= 큐의 길이)가 존재하는 한 큐에서 다음 방문할 노드를 뽑아 줍니다.
4. 뽑은 노드가 이미 방문했던 노드가 아니라면, 해당 노드의 자식 노드들을 큐에 우선 순위로 넣어줍니다.
5. 방문해야 하는 노드가 없어질 때 까지 3-4 과정을 반복해줍니다.

자바스크립트로 DFS 구현하기

const DFS = (graph, firstNode) => {
  const visited = [];
  let needVisit = [];

  needVisit.push(firstNode);

  while (!!needVisit.length) {
    const node = needVisit.shift();
    if (!visited.includes(node)) {
      visited.push(node);
      needVisit = [...graph[node], ...needVisit];
    }
  }

  return visited;
};