ZeroCho Blog

안녕하세요. 이번 시간에는 그래프를 탐색하는 두 가지 방법인 DFS와 BFS에 대해 알아보겠습니다!

그래프 탐색은 그래프 안에 어떤 버텍스들이 있는지 알고 싶을 때 사용합니다. DFS는 버텍스의 자식들을 먼저 탐색하고, BFS는 버텍스의 형제들을 먼저 탐색합니다. 무슨 소리인지 잘 모르겠죠? 아래의 예시를 보시죠.

DFS

Depth First Search의 약자로 깊이 우선 탐색을 뜻합니다. 버텍스의 자식들을 우선으로 탐색한다고 설명했는데 다음과 같은 경우입니다.

버텍스 옆의 숫자는 탐색 순서입니다. A, X 다음에 G, H 선택지가 두 개가 있는데 G와 H를 고른 후(스택에 넣은 후), G는 내버려두고 H의 자식들로 이동합니다. 형제보다는 자식을 우선 탐색하는 겁니다. 모든 자식을 탐색한 후에 이제 스택에 넣어뒀던 형제를 탐색합니다.

그래프는 트리와는 다르게 아크 관계가 얽혀 있어서 누가 부모고 누가 자식인지 쉽게 구별하기 힘듭니다. 이럴 때는 시작점(A)와의 최단거리를 보면 됩니다. X는 A로부터의 거리가 1입니다. G와 H는 A로부터의 거리가 2입니다. 따라서 G와 H는 X의 자식이 됩니다. P와 E는 A로부터의 거리가 3이 됩니다. 따라서 G 또는 H의 자식이 됩니다. 누구의 자식이 될 것인가는 아크 배치 순서에 따라 다릅니다. 저는 P와 E 모두 H의 자식으로 두었습니다.

코드로 볼까요? 스택 코드 와 그래프 코드 를 재사용합니다. 혹시 스택을 까먹으신건 아니죠? 그렇다면 다시 보고 오세요!

이번 시간에는 지난 시간들과는 예시가 좀 달라졌습니다. 잠시 예시를 먼저 만들어볼까요? 이 예시는 아래 BFS에서도 그대로 사용됩니다.

var graph = new Graph();
graph.insertVertex('A');
graph.insertVertex('X');
graph.insertVertex('G');
graph.insertVertex('H');
graph.insertVertex('P');
graph.insertVertex('E');
graph.insertVertex('Y');
graph.insertVertex('M');
graph.insertVertex('J');
insertTwoWayArc(graph, 1, 'A', 'X');
insertTwoWayArc(graph, 1, 'X', 'G');
insertTwoWayArc(graph, 1, 'X', 'H');
insertTwoWayArc(graph, 1, 'G', 'H');
insertTwoWayArc(graph, 1, 'G', 'P');
insertTwoWayArc(graph, 1, 'H', 'E');
insertTwoWayArc(graph, 1, 'H', 'P');
insertTwoWayArc(graph, 1, 'E', 'M');
insertTwoWayArc(graph, 1, 'E', 'Y');
insertTwoWayArc(graph, 1, 'Y', 'M');
insertTwoWayArc(graph, 1, 'M', 'J');

이제 DFS 코드입니다.

Graph.prototype.dfs = function() {
  var stack = new Stack();
  var temp = this.first;
  while (temp) {
    temp.inTree = false;
    temp = temp.next;
  }
  temp = this.first;
  stack.push(temp); // 스택에 첫 버텍스를 넣음
  temp.inTree = true;
  while (stack.count) { // 탐색을 완료할 때까지
    temp = stack.pop(); // 넣었던 버텍스를 하나씩 꺼냄
    console.log(temp.key);
    temp.inTree = true;
    var arc = temp.arc;
    while (arc) {
      if (!arc.destination.inTree) {
        stack.push(arc.destination); // 꺼낸 것과 연결된 버텍스들을 스택에 넣음
        arc.destination.inTree = true;
      }
      arc = arc.nextArc;
    }
  }
};
graph.dfs(); // A, X, H, P, E, Y, M, J, G

inTree 속성을 사용했는데, 정확히는 inTree라고 이름붙인 게 옳지는 않습니다. 그냥 새로운 속성을 주기 귀찮아서 지난 시간의 inTree 속성을 재사용했습니다. 결과는 위의 그림이랑 순서가 같죠?

BFS

Breadth First Search의 약자로 너비 우선 탐색을 뜻합니다. 버텍스의 형제들을 우선으로 탐색한다고 설명했는데 다음과 같은 경우입니다.

아까는 G는 내버려두고 H의 자식들로 갔다면, 이번에는 G부터 처리하고, H를 처리한 후 H의 자식으로 이동합니다. 즉 형제들을 먼저 처리하는 거죠. 다익스트라 알고리즘에서 모든 아크들의 가중치가 1인 경우와 유사합니다.

코드로 볼까요? 큐 코드 와 그래프 코드 를 재사용합니다. 큐를 까먹으셨다면 다시 보고 오세요!

Graph.prototype.bfs = function() {
  var queue = new Queue();
  var temp = this.first;
  while (temp) {
    temp.inTree = false;
    temp = temp.next;
  }
  temp = this.first;
  queue.enqueue(temp); // 첫 버텍스를 큐에 넣음
  temp.inTree = true;
  while (queue.count) { // 탐색을 완료할 때까지
    temp = queue.dequeue(); // 큐에서 하나씩 꺼냄
    console.log(temp.key);
    temp.inTree = true;
    var arc = temp.arc;
    while (arc) {
      if (!arc.destination.inTree) {
        queue.enqueue(arc.destination); // 꺼낸 것과 연결된 버텍스들을 큐에 넣음
        arc.destination.inTree = true;
      }
      arc = arc.nextArc;
    }
  }
};
graph.bfs(); // A, X, G, H, P, E, M, Y, J

BFS도 위의 사진과 같이 동작하죠? DFS가 스택의 특징(LIFO)에 의해 자동으로 깊이 우선 탐색이 되는 반면, BFS는 큐의 특징(FIFO) 때문에 자동으로 너비 우선 탐색이 됩니다.

다음 시간에는 마지막으로 네트워크 플로우에 대해 알아보겠습니다!