그래프 - 그래프의 종류와 표현

#1 그래프

#1-1 그래프

그래프는 현상이나 사물을 정점(Vertex)와 간선(Edge)로 표현하는 것이다. 정점은 어떤 개체를 나타내고, 간선은 그 개체들 간의 관계를 나타낸다. 위 그림은 각 정점(도시)을 항공편(간선)이 잇는 모습을 표현한 예이다. n개의 정점 집합 V와 이들 간에 존재하는 간선의 집합 E로 구성된 그래프 G를 G = (V, E)로 기술한다.
 

#1-2 가중치가 없는 그래프 vs 가중치가 있는 그래프

간선에는 가중치를 줄 수 있다. 항공편으로 비유하자면, 운항비가 가중치가 된다. 가중치가 없는 그래프를 가중치가 있는 그래프처럼 생각할 수도 있다. 모든 가중치를 1로 보면 된다.
 

#1-3 무향 그래프 vs 유향 그래프

항공편은 반드시 양방향적이지는 않다. 예를 들어 런던에서 파리를 갈 수 있지만, 파리에서 런던을 가지 못한다면 유향 그래프로 그 상황을 표현할 수 있다. 서울과 도쿄처럼, 서로 오갈 수 있다면 화살표를 2개 사용한다.

#1-4 가중치가 있는 유향 그래프

유향 그래프에 가중치까지 부여하면 위와 같은 모습이 된다.
 

#2 그래프의 표현 -  인접 행렬 (Adjacency Matrix)

행렬을 이용해 그래프를 표현할 수 있다. 어떤 그래프 G = (V, E)의 정점이 n개라면, 크기가 n × n인 2차원 행렬 A를 준비한다. 어떤 두 정점에서 서로를 잇는 간선이 있다면 두 정점이 서로 인접(Adjacency)한다고 표현한다. 2차원 행렬의 행과 열 각각의 인덱스의 동일한 순서로 정점을 나열한다. 그리고 행렬의 모든 A[x][y] (에 대해 x에서 y로 가는 가중치 값을 할당한다.

만약, 가중치가 없는 그래프라면 A의 모든 원소는 0 또는 1일 것이다. 또 만약, 무향 그래프라면, 행렬은 직선 b를 기준으로 대칭을 이룬다.

이 방법은 직관적이며, 간선의 존재 여부를 A[x][y]를 참조함으로써 즉각 알 수 있다. 하지만, 행렬 저장을 위한 n × n 크기의 공간 그리고, 행렬에 값을 넣기 위한 n × n 크기의 시간이 필요하다. 따라서, 간선의 수가 많지 않은 경우 공간과 시간이 낭비된다.
 

#3 인접 배열 (Adjacency Array)

#3-1 가중치가 없는 무향 그래프의 경우

배열로도 그래프를 표현할 수 있다. 먼저, 정점의 갯수만큼 배열을 선언한다. 각 배열의 0번 원소에는 해당 정점과 연결된 간선(≠정점)의 갯수를 할당한다 (#3-3의 TMI에서 추가 설명).

각 배열에서 0이 아닌 인덱스에는 각 배열이 대변하는 정점에 연결된 정점의 번호를 집어넣는다. 예를 들어, 서울을 대변하는 3번 배열 속 인덱스 1 ~ 3인 원소에는 서울과 연결된 도시인 도쿄, 타이베이, 베이징의 번호 4, 6, 1을 할당한다. 이 때, 각 정점의 번호는 오름차순 또는 내림차 순으로 정렬해 차례대로 할당한다. 정렬된 배열에는 이진탐색을 수행할 수 있기 때문에 어떤 간선을 참조하기 위해 배열을 순회하는 과정을 더 빨리 진행할 수 있다.

간선은 두 정점을 잇는데, 위 그림에서 간선의 갯수는 9개이므로 배열 속 정점의 갯수 즉, 배열 속 주황색 글씨의 갯수는 9 × 2 = 18다. 인접 배열로 그래프를 표현하면, 간선의 갯수에 비례하는 공간과 시간을 점유하기 때문에, 정점에 비해 간선이 적을 때 알뜰하게 사용할 수 있다. 하지만, 정점 대비 간선이 빡빡하게 많은 편이라면 인접 행렬을 사용하는 방법 대비 오히려 오버헤드가 많이 발생한다.

 

#3-2 가중치가 없는 무향 그래프의 경우 (간소화 버전)

위와 같이 간소화 할 수도 있다. #3-1의 0번 인덱스를 생략했지만, 배열의 길이를 참조하면 생략했던 인덱스가 담은 정보와 같은 정보를 얻어낼 수 있기 때문이다.

 

#3-3 가중치가 있는 유향 그래프의 경우

가중치가 있는 유향 그래프라면 다음과 같이 표현할 수 있다. 제일 먼저, 다른 정점으로 갈 수 있는 간선의 갯수(파란 글씨)를 적는다.

 

TMI

#3-1에서도 언급했지만, 간소화 버전이 아닌 경우 인접 배열에서 0번 인덱스는 연결된 정점의 갯수가 아니라, 다른 정점으로 갈 수 있는 간선의 갯수다. 이 사실은 유향 그래프에서 중요하게 기억해두어야 한다. 반드시 양방향으로 연결되는 무향 그래프와 달리, 유향 그래프는 단방향으로도 연결될 수 있다. 예를 들어 위 그래프에서 서울은 베이징과 '연결'되어있지만, 반대로 베이징은 서울과 '연결'되어있지 않은 셈이다. '그래프 분야에서의 연결'이라는 단어는 이렇게 세세하게 따져봐야 하는 것이다. 따라서 "(간소화 버전이 아닌 경우) 0번 인덱스는 다른 정점으로 갈 수 있는 간선의 갯수다!"라고 기억해두자.

 

이후, 연결된 정점의 번호를 의미하는 원소 바로 오른쪽에 가중치 값을 써 넣는다. 따라서, 가중치가 있는 그래프를 인접 배열로 표현하면, 각 배열의 크기는 반드시 홀수다 (1 + 2 × (연결된_간선의_갯수)).

 

#3-4 가중치가 있는 유향 그래프의 경우 (간소화 버전)

#3-2와 같은 맥락으로 간소화가 가능하다.

 

#3-5 인접 배열들을 단일 인접 배열로 변환

#3-3의 0 ~ 6번 배열을 하나로 합칠 수도 있다. #3-3에서 인덱스 0에 해당하는 부분을 파란 글씨처럼 바꾼다. 파란 글씨의 의미는 현재 배열까지 포함해 누적된 정점의 갯수다. 그리고 모든 배열을 하나로 합쳐 singleAdjacencyArray를 만든다. 해당 배열에서 어떤 정점 또는 간선을 참조하는 로직은 많이 복잡하겠지만, 어떤 그래프를 하나의 배열로 변환할 수 있다는 것은 분명한 장점이다.