BFS 와 DFS란?

• 대표적인 그래프 탐색 알고리즘
  • BFS: 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들을 먼저 순회
  • DFS: 한 노드의 자식을 타고 끝까지 순회 후, 다시 돌아와서 다른 형제의 자식을 타고 내려가며 순회

BFS: A - B - C - D - E - F
DFS: A - B - D - E - C - F

// 그래프로 구현
const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'],
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B']
}

graph 구현

class Graph {
  constructor(value) {
    this.value = value;
  }
  
  bfs(graph, startNode) {...}
  dfs(graph, startNode) {...}
}
const graphBfsDfs = new Graph();

graphBfsDfs.bfs(graph, "A");
graphBfsDfs.dfs(graph, "A");

BFS 구현

• Queue를 이용해 구현
• 시작 지점에서 가까운 정점부터 탐색
• V는 정점의 수, E는 간선의 수 -> 시간복잡도 = $O(V+E)$

bfs(graph, startNode) {
    const visited = [];
    let need_visit = [];

    need_visit.push(startNode);

    while (need_visit.length > 0) {
      const currNode = need_visit.shift();
      if (!visited.includes(currNode)) {
        visited.push(currNode);
        const nodeArr = Object.assign([], graph[currNode]); 
        //graph[currNode]는 객체여서 iterable하지 않아 배열로 바꿔줌
        need_visit = [...need_visit, ...nodeArr];
      }
    }
    console.log(visited); // [ 'A', 'B', 'C', 'D', 'E', 'F' ]
  }

Queue 코드

DFS 구현

• Stack을 이용해 구현
• 시작 정점에서 자식을 타고 깊숙한 끝까지 순회
• 시간복잡도 $O(V+E)$

dfs(graph, startNode) {
    const visited = [];
    let need_visit = [];

    need_visit.push(startNode);

    while (need_visit.length > 0) {
      const currNode = need_visit.shift();
      if (!visited.includes(currNode)) {
        visited.push(currNode);
        const nodeArr = Object.assign([], graph[currNode]); 
        //graph[currNode]는 객체여서 iterable하지 않아 배열로 바꿔줌
        need_visit = [...nodeArr, ...need_visit];
      }
    }
    console.log(visited); // [ 'A', 'B', 'D', 'E', 'C', 'F' ]
  }