DFS, BFS 활용과 다익스트라

BFS, DFS 두가지 모두 그래프를 탐색(Graph Traverse)하는 방법입니다.

그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며, 그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.

---

BFS

graph = {
  'A' : ['B','C'],
  'B' : ['A', 'D'],
  'C' : ['A', 'E'],
  'D' : ['B', 'E', 'F'],
  'E' : ['C', 'D', 'F'],
  'F' : ['D', 'E']
};

bfs(start_vertex = "A") {
  const queue = [start_vertex];
  const result = [];
  const visited = {};
  let currentVertex;
  visited[start_vertex] = true;

  while(queue.length) {
    currentVertex = queue.shift();
	result.push(currentVertex);
    
    graph[currentVertex].forEach(neighbor => {
     if(!visited[neighbor]) {
       visited[neighbor] = true;
       queue.push(neighbor);
     }
    });
  }
  return result;
}

DFS

graph = {
  'A' : ['B','C'],
  'B' : ['A', 'D'],
  'C' : ['A', 'E'],
  'D' : ['B', 'E', 'F'],
  'E' : ['C', 'D', 'F'],
  'F' : ['D', 'E']
};

dfs(start_vertex = "A") {
  const stack = [start_vertex];
  const result = [];
  const visited = {};
  let currentVertex;
  
  visited[start] = true;
  while(stack.length) {
    currentVertex = stack.pop();
    result.push(currentVertex);
    
    graph[currentVertex].forEach(neighbor => {
     if(!visited[neighbor]) {
         visited[neighbor] = true; 
         stack.push(neighbor);
       }
    });
  }
  return result;
}

recursive_dfs(start_vertex = "A") {
  const result = [];
  const visited = {};
  
  (function dfs(vertex) {
    if(!vertex) return null;
    visited[vertex] = true;
    result.push(vertex);
    graph[vertex].forEach(neighbor => {
     if(!visited[neighbor]) {
      return dfs(neighbor);  
     }
    });
  })(start_vertex);
  
  return result; 
}

---

언제 DFS, BFS를 이용하나요?

문제 유형별로 어떤 알고리즘이 더 유리한지 서술한다.

• 🚫 : impossible
• 👍 : good and possible
• 👎 : bad but possible

index	Problem	BFS	DFS
1	그래프의 모든 정점을 방문 하는 문제	👍	👍
2	각 경로마다 특징을 저장해둬야 하는 문제	👎	👍
3	최단거리 문제	👍	👎
4	문제의 그래프가 매우 클 경우	🚫	👍
5	검색 시작 지점과 원하는 대상이 가까이 있을 경우	👍	👎