DFS and BFS

간단하게 bfs와 dfs를 javascript 로 구현해보고, 상황별 장단점을 분석해본다.

1. Graph Traverse

1.1. 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;
}

1.2. 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; 
}

1.3. BFS vs DFS

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

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

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