그래프 : 종류와 표현법

1. 그래프의 종류

유향 그래프 (Directed Graph) : 그래프의 방향을 가진다.

무향 그래프 (Undirected Graph) : 간선의 방향이 없다

n개의 정점 집합 V와 이들간의 존재하는 간선의 집합 E로 구성된 그래프 G를 G = (V,E)로 표시한다.

 

2. 그래프의 표현

1) 인접행렬을 이용

그래프 G = (V,E)에서 정점의 총수가 n이라고 하고 정점 i와 정점 j 사이에 간선이 있으면 그때 1이라고 한다. 위와 같은 무향 그래프에서는 양쪽 방향으로 다 갈 수 있음으로 (i,j)와 (j,i)가 같은 대칭으로 나타나지만 유향은 아닐 수 있다. 

 

행렬표현법의 장점은 간선의 존재여부를 즉각 알 수 있다는 것이지만 n*n 행렬을 채워야됨으로 n^2에 비례하는 공간이 필요하고 행렬의 모든 원소를 채우는데 O(n^2)이 필요하다. 

 

2) 인접리스트 이용

 

각 정점마다 리스트를 하나씩 만들고 여기에 각 정점에 인접한 정점들을 연결 리스트로 매단다. 행렬 표현법에서는 존재하지 않는 간선도 0으로 표현했지만 인접리스트는 있는 간선만 표현한다. 

또한 각 노드는 <정점번호, 가중치, 다음 정점의 포인터>로 구성된다. 

 

인접리스트는 공간의 낭비가 없어 간선의 수가 적을 때 유용하다. 하지만 간선이 많을 경우 i, j 사이에 간선이 존재하는지 알아볼때 인접 리스트에서 차례로 훑어야 함으로 시간이 많이 걸리게 된다. 최악의 경우에는 만일 한곳에 다 몰려있을때 O(n)의 시간이 걸리게 된다. 

 

3) 인접 배열과 인접 해시 테이블

위처럼 인접 배열의 헤더에 원소의 갯수를 표시하고 그것을 연결된 정점들이 모인 배열과 연결하는 것이다. 위의 장점은 연결 리스트의 포인터를 관리안해도 되고 두 정점의 인접여부 체크하는 것 역시 쉬워진다.

또한 i에 j의 정점이 연결되어있는지 확인할때 만약 인접배열에 정렬이 되어있다면 이진 탐색을 사용할 수 있어 logn안에 찾을 수 있다.