이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

게시글

강좌16 - Algorithm - 2년 전 등록

그래프(graph)

자료구조
조회수:
0
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

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

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

그래프는 버텍스 간에 여러 개의 아크가 존재할 수 있습니다. 다른 버텍스에서부터 오는 아크의 개수를 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도 나중에 네트워크 플로우 때 할 예정입니다.

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

목록
투표로 게시글에 관해 피드백을 해주시면 많은 도움이 됩니다. 오류가 있다면 어떤 부분에 오류가 있는지도 알려주세요! 잘못된 정보가 퍼져나가지 않도록 도와주세요.
Copyright © 2016- 무단 전재 및 재배포 금지

댓글

4개의 댓글이 있습니다.
2달 전
1 -> 4 로 가는 아래의 경우,
1 -> 3 -> 4 가 최단 경로이지만, 이런 경우를 못찾네요.
graph.insertArc(100, '1', '2');
graph.insertArc(1, '1', '3');
graph.insertArc(10, '2', '3');
graph.insertArc(1, '2', '4');
2달 전
3에서 4 경로가 없는 것 아닌가요?
3달 전
arc의 capacity 프로퍼티의 역할은 무엇인가요??
3달 전
아크는 파이프라고 생각하시면 됩니다. 수도관이 있다면 흐를 수 있는 물의 최대량입니다.
3달 전
일반적으로 자료구조에서 같은 데이터를 여러번 입력할 수 있도록 하는 것이 좋은가요?

예를 들어..
graph.insertVertex('A');
graph.insertVertex('A');
graph.insertVertex('A');
graph.insertVertex('A');
graph.insertVertex('A');
graph.insertArc(1, 'A', 'A');

이런식으로 함수를 실행하면 어떤 vertext에 arc가 연결되는지 명확하지가 않게 되어버리는데 그런 부분은 어떻게 처리하는게 좋을지 궁금합니다.
3달 전
음.. insert 전에 미리 A라는 버텍스가 있는지 검사하신 후 없을 때 넣으시면 될 것 같습니다.
3달 전
방향이 없는 그래프를 만들게 되면 서로 양쪽으로 연결되는데 코드로 구현하게 되면 객체가 무한으로 연결되어 있게 되는건가요? (prototype과 constructor처럼..)

A.arc = B
B.arc = A
..
3달 전
네네 그래야 서로로 이동 가능합니다.