ZeroCho Blog

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

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

들어가기에 앞서

댓글에서 많은 논쟁이 있었는데요. 우선 제 블로그 포스팅은 틀린 점이 없다는 것을 알려드립니다. 다만 여러분들이 오해하는 것(또는 저와 생각이 다를 수 있는 것) 두 가지를 알려드립니다.

첫 번째 오해는 제 포스트를 트리의 DFS라고 생각하는 것입니다. 그래프의 DFS와 트리의 DFS는 다를 수 있습니다. 트리는 보통 끝점이 명확하므로 끝까지 파고들 수 있지만, 그래프에서는 끝점이 명확하지 않은 경우가 많아 어느 순간에 탐색을 멈출지를 정해야 합니다.

여기서 두 번째 오해가 나옵니다. 알고리즘이 하나라고 생각하실 수 있지만, 그래프의 경우는 어느 순간에 멈추느냐에 따라 다양한 알고리즘이 나올 수 있습니다. 제가 선택한 것은 무작정 끝까지 달리는 것도 아니고 하나의 숫자로 정해진 뎁스까지 가는 것도 아니고 스택에 이미 들어있는 요소를 만날 때까지 달리는 것입니다.

이렇게 가정하면 오해가 없으실 것이라 생각되네요. 대학생분들이 많이 찾아오시는 것으로 보이는데 제가 정한 기준과 다른 DFS를 구현하시고 싶으시면 다른 블로그를 찾아가세요.

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) 때문에 자동으로 너비 우선 탐색이 됩니다.

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