ZeroCho Blog

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

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

들어가기에 앞서

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

첫 번째 오해는 제 포스트를 일반적인 트리의 DFS라고 생각하는 것입니다. 그래프의 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) 때문에 자동으로 너비 우선 탐색이 됩니다.

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