게시글

5만명이 선택한 평균 별점 4.9의 제로초 프로그래밍 강좌! 로드맵만 따라오면 됩니다! 클릭
강좌16 - Algorithm - 7년 전 등록 / 5달 전 수정

그래프(graph)

자료구조

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

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

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

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

undefined

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

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

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

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

undefined

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

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

undefined

undefined

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

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

const 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.nextArc;
    }
    if (!fromArc) return false;
    if (preArc) {
      preArc.nextArc = fromArc.nextArc;
    } else {
      from.arc = fromArc.nextArc;
    }
  };
  return Graph;
})();
const 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도 나중에 네트워크 플로우 때 할 예정입니다.

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

조회수:
0
목록
투표로 게시글에 관해 피드백을 해주시면 게시글 수정 시 반영됩니다. 오류가 있다면 어떤 부분에 오류가 있는지도 알려주세요! 잘못된 정보가 퍼져나가지 않도록 도와주세요.
Copyright 2016- . 무단 전재 및 재배포 금지. 출처 표기 시 인용 가능.
5만명이 선택한 평균 별점 4.9의 제로초 프로그래밍 강좌! 로드맵만 따라오면 됩니다! 클릭

댓글

9개의 댓글이 있습니다.
5달 전
deleteVertex 메서드에서 key와 같은 vertex를 찿는 코드 있잖아요...

while (vertex.key !== key) {
prev = vertex;
vertex = vertex.next;
}

이 부분이요

여기서 만약 찾는 Key가 graph에 없다면 중간 오류가 발생할 것 같은데
graph에 등록된 Key만 삭제한다고 전제하면 되나요?

그리고 왜 vertex의 arc가 null이면 false를 반환하는지 궁금합니다 ㅎ

아! 그리고 delete_arc 메서드에서

while (fromArc !== null) {
if (toKey === fromArc.destination.key) break;
preArc = fromArc;
fromArc = fromArc.next;
}

이 부분에서 fromArc = fromArc.next => fromArc = fromArc.nextArc로 수정해야 할 것 같네요 ㅎ
5달 전
감사합니다. 존재하는 vertex만 삭제한다고 가정했다고 보시면 됩니다. false 부분은 다른 값이든 에러든 메시지든 원하시는 걸로 바꿔도 됩니다.
5달 전
헐... 오래전 글이라 답변 안달릴 수도 있겠다 생각했었는데 엄청 빨리 답해주셨네요 ㅎ
감사드립니다 ㅎㅎ

>> 그리고 왜 vertex의 arc가 null이면 false를 반환하는지 궁금합니다 ㅎ
이 질문에서 제가 질문의 요지를 정확하게 말씀 못드린 것 같아요
번거로우시겠지만 한번 더 질문드릴께요

delete_vertex 메서드에서 vertex의 arc가 없으면 중간에 return되서 실제 vertext가 삭제 되지 않잖아요... 왜 vertex의 arc가 없으면 vertex가 삭제되지 않아야 하는지가 궁금합니다
5달 전
이게 제 대학교 교재를 따라서 한 거라서 정확한 이유가 기억이 나지 않네요. 불필요한 경우 제거하셔도 됩니다.
5달 전
네 답변 감사드립니다 ㅎ
2년 전
위 코드에서 버텍스 A를 살펴볼때 B랑만 연결되어 있습니다.
graph.first.key 가 A 이고
graph.first.arc.destination.key가 B이고
여기까지는 이해가 되는데
graph.first.arc.destination.arc.destination.key가 C인것은 이해가 되지 않습니다.
A는 B랑만 연결되어 있는 것이 아닌지요?
제가 뭘 잘못 이해하고 있는지 잘 모르겠습니다. 도와주시면 감사하겠습니다.
2년 전
graph.first.arc.destination는 B입니다.
graph.first.arc.destination.arc.destination.key는 B.arc.destination.key이므로 C입니다.
2년 전
답변 감사합니다. 제로초님.
그렇다면 A는 B랑만 연결 되어있다는 것을 어떻게 알 수 있나요?
알 필요가 없는 부분인가요?
생각해보니 직접적으로 연결되어 있지 않더라도 타고타고 가면 만나는 것이기 때문에 계속해서 연결 되는 것 같습니다. 저는 연결 리스트만 생각해서 각각 나눠 져 있는 것으로 착각한 것 같습니다.
제로초님 답변 덕분에 그래프에 대해 조금 더 이해가 되는 것 같습니다.
감사합니다.
5년 전
중간에 '이차원 배열은 버텍스 개수(V)의 제곱에 해당하는 공간을 차지합니다. 이차원 배열은 버텍스 개수와 아크 개수(E)의 합에 해당하는 공간만 차지합니다.' 라고 써져있는데 연결리스트를 이차원배열이라고 잘못 쓰신거같아요. 요즘 알고리즘 공부하는데 도움이 많이 되고있어요!
5년 전
댓글들이 왜이리 어딘가 아파보이는 사람들이...있죠
5년 전
자료타입과는 전혀 관련없지만 Arch를 발음할때 \u003cɑːrtʃ>로 발음합니다. \u003ctʃ>는 무성 치조후 파찰음이고 굳이 한글로 적자면 \u003cㅌㅊㅟ>정도입니다. 더 보기 좋게 적자면 \u003c치>겠죠. 때문에 본문에 있는 \u003c아크>를 \u003c아치>로 수정 요청하는 바입니다.
5년 전
arch가 아니라 arc입니다.
6년 전
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');
6년 전
3에서 4 경로가 없는 것 아닌가요?
6년 전
arc의 capacity 프로퍼티의 역할은 무엇인가요??
6년 전
아크는 파이프라고 생각하시면 됩니다. 수도관이 있다면 흐를 수 있는 물의 최대량입니다.
6년 전
일반적으로 자료구조에서 같은 데이터를 여러번 입력할 수 있도록 하는 것이 좋은가요?

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

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

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