ZeroCho Blog

안녕하세요. 이번 시간에는 그래프에 대해 알아보겠습니다. 그래프는 이후에 나올 많은 알고리즘에서 사용되기 때문에 꼭 알아두셔야 합니다.

그래프는 트리와 비슷하게 노드와 엣지로 구성되어 있습니다. 그래프에서는 노드를 버텍스, 엣지를 아크라고 부릅니다. 사실 그냥 노드랑 엣지로 불러도 상관 없지만, 있어보이려면 버텍스와 아크로 부르도록 합시다.

그래프는 버텍스 간에 여러 개의 아크가 존재할 수 있습니다. 다른 버텍스에서부터 오는 아크의 개수를 In-degree, 다른 버텍스로 가는 아크의 개수를 Out-degree라고 부릅니다. 또한 방향성을 띄고 있는지에 따라 방향 그래프와 무방향 그래프로 나뉩니다.

트리는 사실 그래프의 특수한 형태입니다. 트리는 하나의 부모 노드에서부터 아래 방향으로 내려오는 그래프입니다. 즉, 트리를 루트가 있고 In-degree가 1인 방향 그래프라고 말할 수 있습니다. 일반 그래프는 그 제약이 없습니다. 다음과 같은 그래프들을 보시죠.

 

왼쪽은 방향 그래프이고, 오른쪽은 무방향 그래프입니다. 방향 그래프는 방향을 나타내는 화살표가 있습니다. 트리도 방향 그래프라서 화살표를 표시해야 하지만 그냥 지금까지 생략했던 겁니다.

트리의 노드가 하나의 In-degree만 가지는 반면, 그래프의 버텍스는 하나 이상의 In-degree를 가질 수 있습니다. 예를 들면 왼쪽 방향 그래프에서, E 버텍스는 B와 C로부터 오는 두 개의 In-degree와 D와 F로 가는 두 개의 Out-degree를 가지고 있습니다.

오른쪽 무방향 그래프는 양쪽으로 모두 이어져 있습니다. 이런 무방향 그래프는 E 버텍스의 경우 그냥 4개의 Degree가 있다고 말합니다.

모든 버텍스가 아크로 연결된 그래프를 완전 그래프라고 부릅니다. 그리고 그래프의 부분집합을 부분 그래프라고 부릅니다. 다음은 하나의 완전 그래프와 그 부분 그래프의 모양입니다.

 

그래프를 코드로 표현하는 방법에는 크게 두 가지가 있는데 하나는 이차원 배열을 사용하는 방법과, 다른 하나는 연결 리스트를 사용하는 방법이 있습니다.

이차원 배열을 사용하면 공간은 많이 차지하지만 간단하고, 연결 리스트는 공간은 적게 차지하지만 복잡합니다. 다음 그림들을 보시죠.

 

 

이차원 배열은 버텍스 개수(V)의 제곱에 해당하는 공간을 차지합니다. 이차원 배열은 버텍스 개수와 아크 개수(E)의 합에 해당하는 공간만 차지합니다. 따라서 버텍스 개수가 작으면 이차원 배열, 크면 연결 리스트를 사용하는 게 효율적일 수 있습니다.

우리는 고통받는 프로그래머이므로 연결 리스트를 사용합니다. 자바스크립트 코드로 나타내봅시다. 방향 그래프를 구현할 겁니다.

var Graph = (function() {
  function Vertex(key) {
    this.next = null;
    this.arc = null;
    this.key = key;
    this.inTree = null;
  }
  function Arc(data, dest, capacity) {
    this.nextArc = null;
    this.destination = dest;
    this.data = data;
    this.capacity = capacity;
    this.inTree = null;
  }
  function Graph() {
    this.count = 0;
    this.first = null;
  }
  Graph.prototype.insertVertex = function(key) {
    var vertex = new Vertex(key);
    var last = this.first;
    if (last) {
      while (last.next !== null) {
        last = last.next;
      }
      last.next = vertex;
    } else {
      this.first = vertex;
    }
    this.count++;
  };
  Graph.prototype.deleteVertex = function(key) {
    var vertex = this.first;
    var prev = null;
    while (vertex.key !== key) {
      prev = vertex;
      vertex = vertex.next;
    }
    if (!vertex) return false;
    if (!vertex.arc) return false;
    if (prev) {
      prev.next = vertex.next;
    } else {
      this.first = vertex.next;
    }
    this.count--;
  };
  Graph.prototype.insertArc = function(data, fromKey, toKey, capacity) {
    var from = this.first;
    var to = this.first;
    while (from && from.key !== fromKey) {
      from = from.next;
    }
    while (to && to.key !== toKey) {
      to = to.next;
    }
    if (!from || !to) return false;
    var arc = new Arc(data, to, capacity);
    var fromLast = from.arc;
    if (fromLast) {
      while (fromLast.nextArc != null) {
        fromLast = fromLast.nextArc;
      }
      fromLast.nextArc = arc;
    } else {
      from.arc = arc;
    }
  };
  Graph.prototype.deleteArc = function(fromKey, toKey) {
    var from = this.first;
    while (from !== null) {
      if (from.key === fromKey) break;
      from = from.next;
    }
    if (!from) return false;
    var fromArc = from.arc;
    var preArc;
    while (fromArc !== null) {
      if (toKey === fromArc.destination.key) break;
      preArc = fromArc;
      fromArc = fromArc.next;
    }
    if (!fromArc) return false;
    if (preArc) {
      preArc.nextArc = fromArc.nextArc;
    } else {
      from.arc = fromArc.nextArc;
    }
  };
  return Graph;
})();

var graph = new Graph();
graph.insertVertex('A');
graph.insertVertex('B');
graph.insertVertex('C');
graph.insertVertex('D');
graph.insertVertex('E');
graph.insertVertex('F');
graph.insertArc(1, 'A', 'B');
graph.insertArc(1, 'B', 'C');
graph.insertArc(1, 'B', 'E');
graph.insertArc(1, 'C', 'E');
graph.insertArc(1, 'C', 'D');
graph.insertArc(1, 'E', 'D');
graph.insertArc(1, 'E', 'F');

Vertex는 Vertex끼리 연결리스트를 취하고 있고, 각각의 Vertex는 자신과 연결된 Arc에 대한 연결리스트도 가지고 있습니다. 위의 그래프는 방향 그래프이기 때문에 한쪽 방향으로만 연결되어 있습니다. 만약 무방향 그래프를 만들고 싶으시면 다음과 같은 함수를 만들어 양쪽 방향으로 연결해주면 됩니다.

function insertTwoWayArc(graph, data, from, to) {
  graph.insertArc(data, from, to);
  graph.insertArc(data, to, from);
}

Arc의 data는 나중에 가중치(weight)으로도 사용됩니다. 그렇기 때문에 겹칠 수도 있어서 Vertex처럼 key를 사용하지 않았습니다.

inTree는 아직 한 번도 사용은 안 했지만 나중에 MST나 다익스트라 알고리즘을 할 때 사용하려고 만들어둔 겁니다. 조금만 기다려주세요. capacity도 나중에 네트워크 플로우 때 할 예정입니다.

다음 시간에는 다시 알고리즘으로 돌아가서 동적 프로그래밍에 대해 알아보겠습니다.