그래프

개요

정점(vertex, 노드, 포인트) 들과 이들 사이의 연결관계를 표현한 추상적 개념 및 자료구조 입니다.

그래프의 표현은 아래의 그림과 같이 정점과 이들을 잊는 간선(edge)의 집합으로 나타냅니다.

용어

경로

간선으로 연결된 정점의 순서를 의미합니다.

순환

한 정점에서 시작하여 그 정점 자신으로 돌아오는, 길이가 3 이상인 경로를 의미합니다.

연결된 그래프

모든 정점에 대해서 그래프 내의 다른 정점과 연결된 경로가 있다면 연결된 그래프라고 부릅니다.

완전그래프

그래프의 모든 두 정점쌍이 하나의 간선으로 연결된 그래프 입니다.

트리

순환이 존재하지 않는 그래프입니다.

종류

그래프는 다음과 같이 3가지 종류로 나누어 볼 수 있습니다.

무향 그래프 (Undirected Graphs)

각 정점을 연결하는 간선이 단순히 두 정점간의 연결을 표현하는 경우 입니다.

유향 그래프

간선이 정점간의 연결 뿐만 아니라 방향을 갖는 그래프입니다.

가중치 그래프

간선에 가중치값(또는 비용)이 추가된 그래프 입니다. 예를 들어 도시간의 연결된 도로를 표시하는 경우 간선에 두 도시간의 거리를 함께 표시한다면 이것이 가중치가 표시된 그래프 입니다.

표현

우선 그래프를 이용하여 문제를 해결하기 위해서는 그래프를 기술한 내용에서 필요한 정보를 뽑아 가공하기 좋도록 저장해야 할 것입니다.

위 그림과 같은 그래프(G)는 다음과 같이 기술됩니다. 정점(V), 간선(E)에 대한 정보가 포함되어 있습니다.

V = { 0, 1, 2, 3, 4 }
E = { (0,1), (0,2), (0,3), (1,2) }
G = {V, E}

이를 컴퓨터를 이용하여 문제를 해결할 수 있도록 자료구조로 표현하도록 합니다. 널리 알려진 그래프를 표현하는 방법은 3가지가 있습니다.

간선리스트(Edge lists)
간단한 방법으로 간선 E 를 나열하는 방법이 있습니다. 간단하지만 그래프에 포함되어 있는 정점에 대한 정보가 누락되어 있기 때문에 사용에 한계가 있습니다. 예를들어 다른 정점과 연결되어 있지 않는 정점에 대한 정보가 정확히 포함되지 않습니다.

l[e][2] = { {0,1},
		    {0,2},
		    {0,3},
		    {1,2} }

인접행렬(adjacency matrix)
인접행렬은 V x V 정점의 크기를 갖는 2차원 배열로 그래프를 표현한 것입니다.
각 열과 행의 인덱스가 정점의 번호를 나타냅니다. adj[i][j] 의 값은 각 정점 사이에 연결되는 간선이 있을 경우는 1 (true), 없을 경우는 0 (false) 로 표현합니다.

adj[v][v] = 
   { {0, 1, 1, 1},
     {1, 0, 1, 0},
     {1, 1, 0, 0},
     {1, 0, 0, 0} }

(위의 예를 든 그래프는 무향 그래프이므로 1과 2가 연결된 경우, 반대로 2와 1이 연결되었다 표시하기 위하여 양측 모두 1(true) 로 표시합니다.)

인접리스트(array of adjacency lists)
정점과 직접적으로 연결된 다른 정점을 표현한 것입니다. 그래프 상의 정점이 v 개 일때 하나의 정점과 연결된 다른 정점의 최대갯수는 v-1 이므로 adj[v][j-1] 의 2차원 배열로 표현 할 수도 있으나, 이럴 경우 메모리 낭비를 피하기 위하여 인접리스트 구조를 택한 장점이 사라지므로 연결리스트(linked list)를 이용하여 표현합니다.

#define NC	99
adj[v][v-1] = 
{ {1, 2, 3},
  {0, 2, NC},
  {0, 1, NC},
  {0, 0, NC} }