깊이 우선 탐색 (DFS)과 너비 우선 탐색 (BFS)

 

깊이 우선 탐색 (Depth First Search)

깊이 우선 탐색은 특정 노드에서 시작해, 최대한 깊숙히 탐색한 후에 다른 분기의 노드를 탐색하는 방식을 말합니다.

 

아래의 그림을 보면 조금 더 이해하기 쉬우실 것입니다. 특정 노드에서 맨 아래의 자손 노드까지 탐색한 후에 목표를 찾지 못했다면 다시 부모 노드로 돌아와 다른 갈림길에서 탐색을 반복합니다. 이때, 부모 노드로 돌아오는 과정을 백트래킹이라고 합니다.

깊이 우선 탐색은 다음과 같은 특징을 가집니다.

1. 모든 경로를 방문해야 할 경우에 적합합니다.
2. 주로 스택을 사용하여 구현합니다.

장점으로는 탐색 경로의 노드들만 기억하면 되므로, 그래프 높이 만큼의 공간만 필요하다는 장점을 가집니다.

단점으로는 목표가 되는 데이터가 없는 경로를 탐색하는 경우가 있다는 것입니다. 목표를 찾는 탐색의 경로가 최단 경로가 아닐 수 있다는 것입니다.

 

자바스크립트 코드

아래의 dfs 탐색입니다.

const graph = {
  '1': ['2', '5', '9'],
  '2': ['1', '3'],
  '3': ['2', '4'],
  '4': ['3'],
  '5': ['1', '6', '8'],
  '6': ['5', '7'],
  '7': ['6'],
  '8': ['5'],
  '9': ['1', '10'],
  '10': ['9'],
};

let unvisited =[];
let visited = [];

function dfs(graph, start){
  unvisited.push(start);
  
  while(unvisited.length !== 0){
    const node = unvisited.pop();
    
    if(!visited.includes(node)){
      visited.push(node);
      unvisited = [...unvisited, ...graph[node]];
    }
  }
  
  return visited;
}

console.log(dfs(graph, "1"));

 

 

너비 우선 탐색 (Breadth First Search)

너비 우선 탐색은 특정 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법입니다.

 

아래의 그림을 보면 조금 더 이해하기 쉬우실 것입니다. 자신과 가까운 노드들을 먼저 탐색하고 그 다음 깊이의 노드들을 탐색하는 방식으로 멀리 떨어져 있는 노드들을 가장 나중에 탐색하는 방식입니다.

깊이 우선 탐색은 다음과 같은 특징을 가집니다.

1. 모든 노드를 탐색하는 것이 아닌 노드 간에 최단 거리를 찾을 때 적합합니다.
2. 주로 큐를 사용하여 구현합니다.

장점으로는 목표 노드를 찾는데 있어 최단 거리로 탐색합니다.

단점으로는 최악의 경우 모든 노드를 탐색해야하는 경우가 생겨, 모든 노드에 대한 공간이 필요할 수 있습니다.

 

자바스크립트 코드

아래의 bfs 탐색입니다.

const graph = {
  '1': ['2', '5', '9'],
  '2': ['1', '3'],
  '3': ['2', '4'],
  '4': ['3'],
  '5': ['1', '6', '8'],
  '6': ['5', '7'],
  '7': ['6'],
  '8': ['5'],
  '9': ['1', '10'],
  '10': ['9'],
};

let unvisited =[];
let visited = [];

function bfs(graph, start){
  unvisited.push(start);
  
  while(unvisited.length !== 0){
    const node = unvisited.shift();
    if(!visited.includes(node)){
      visited.push(node);
      unvisited = [...unvisited, ...graph[node]];
    }
  }
  
  return visited;
}

console.log(bfs(graph, "1"));