그래프(Graph)

그래프의 개념

그래프는 현상이나 사물을 정점과 간선으로 표현하는 것이다.

정점(Vertex)은 대상이나 개체를 나타내고 간선(Edge)은 이들 간의 관계를 나타낸다.

예를 들어, 사람 간의 친밀도를 나타내고 싶다고 하자. 각 사람을 하나씩의 정점으로 표시한다. 서로 친말한 사람 간에는 간선을 둔다. 그러면

 

그림 1

과 같은 그래프가 된다. 각 간선은 간선으로 연결된 두 사람이 친밀함을 나타낸다. 간선은 두 도시를 연결하는 도로의 존재 여부, 두 집안 간의 혼인 여부 등을 나타낼 수 있다.

 

 

 

그림 2

그림 2는 그림 1을 조금 변형한 것이다. 그림 1이 사람 간의 친물도 존재 여부만 표시하는 데 비해 그림 2는 친밀도의 크기까지 표시한다. 즉, 간선에 가중치를 주어 친밀감의 정도를 보여준다. 이런 가중치는 도시 간의 거리, 두 지점 사이에 묻힌 가스 파이프의 용량, 두 공항 사이의 비행 시간 등을 나타낼 수 있다.

 

 

그림 3

 

그림 3은 간선이 방향을 갖는 예를 보여준다.  그림 1과 비교해 간선에 방향성의 개념이 들어간 것만 다르다. 즉, 각 사람이 다른 사람에게 애정을 가지고 있는지 표시했다. 애정의 유무는 상호 대칭적이지 않기 때문에 방향을 가진 간선으로 나타낼 수 있다. 방향을 가진 간선은 기업 간의 제품 공급 관계, 제품 생산 공정에서 선후 관계 등을 나타낼 수 있다. 그림1과 같은 그래프로는 나타낼 수 없는 일방통행 도로의 존재를 나타낼 수도 있다. 이런 그래프를 방향을 가진 그래프 또는 유향 그래프(Directed graph)라고 한다. 반면, 간선의 방향이 없는 그래프를 무향 그래프(Undirected Graph)또는 무방향 그래프라고 한다.

 

그림 4

그림 4는 그림 3의 방향을 가진 간선이 가중치를 갖는 경우다. 누가 누구를 얼만큼 좋아하는지 나타낸다. 서울과 LA 간의 비행기 노선처럼 가는 데 걸리는 시간과 오는 데 걸리는 시간이 다른 경우를 나타낼 수도 있다.

 

그래프의 표현

1. 인접 행렬을 이용한 방법

 

여기서 N은 정점의 총 수 이다.

 

그래프 예시

 

 

2. 인접 리스트를 이용한 방법

 

 

그래프 예시

 

 

3. 인접 배열

그래프 예시

 

 

 

인접 행렬과 인접 리스트의 차이점 

 

인접 행렬은 n*n의 행렬이 필요하므로 n^2에 비례하는 공간이 필요하고 행렬의 준비 과정에서 행렬의 모든 원소를

채우는 데만 n^2의 시간이 든다. 그러므로 O(n^2) 미만의 시간이 소요되는 알고리즘이 필요한 경우에 행렬 표현법을

사용하면 행렬의 준비 과정에서만 Θ(n^2)의 시간을 소모하므로 적절하지 않다.

 

인접 리스트는 공간이 간선의 총수에 비례하는 양만큼 필요하므로 대체로 행렬 표현에 비해 공간의 낭비가 없다.

모든 가능한 정점 쌍에 대해 간선의 수가 적을 때 특히 유용하다. 그렇지만 거의 모든 정점 쌍에 대해 간선이 존재하는

경우에는 오히려 리스트를 만드는 데 필요한 오버헤드만 더 든다. 인접 리스트는 정점 i와 정점 j간에 간선이 존재하는지

알아볼 때 리스트에서 차례대로 훑어야 하므로 인접 행렬 표현보다는 시간이 많이 걸린다. 특히 간선이 많은 경우에는

최악의 경우 n에 비례하는 시간이 들 수도 있다. 이 부분이 이를 이용하는 알고리즘의 성능에 치명적인 영향을 미칠 수

있다. 그래서 인접 리스트 표현법은 간선의 밀도가 아주 높은 경우에는 그리 적합하지 않다. 이때는 인접 행렬 표현법을

쓰는 것이 좋다.

 

 

인접 배열과 인접 해시 테이블 차이점

 

인접 리스트처럼 간선의 수에 비례하는 공간을 쓰면서 간선의 존재 여부를 훨씬 더 빨리 체크하는 방법이 인접 배열이다. 각 정점에 연결된 장점들을 여녈 리스트로 저장하는 대신 배열로 저장하면 연결 리스트의 포인터를 관리하는 번거로움에서 해방될 뿐만 아니라 두 정점의 인접 여부를 체크하는 시간도 대폭 줄일 수 있다.  배열을 정렬된 형태로 만들면 이진 탐색을 쓸 수 있어 임의의 정점에 인접한 정점 수가 k라면 log2k+1번 이내에 비교로 j의 존재를 확인할 수 있다.

 

하지만 다루어야 할 그래프가 엄청난 크기면 이진 탐색을 한다고 해도 자주 하는 것은 힘들다. 예를들어 아주 큰 그래프에서 인접 배열의 평균 크기가 100만이라면 이진 탐색을 해도 최대 22번의 비교가 필요하다.  이럴때 각 인접 배열을 하나씩 해시 테이플로 대체하는 방법도 있다. 각 인접 배열 크기의 두 배 정도의 공간을 할당하여 적재율을 0.5로 만들면 평균 2번 이내의 비교로 가능하다. 원소 집합이 고정된 해시 테이블이므로 어느 정도 충돌이 일어나는지 미리 알 수 있다. 적재율도 미리 마음대로 정할 수 있다. 인접 배열의 두 배 공간도 인접 리스트에 준하는 크기다. 

 

하지만 해시 테이블을 사용할 경우에는 앞의 다른 방법들과 다리 어떤 정점에서 인접한 정점들을 차례로 보면서 작업을 해야 할 경우는 적합하지 않다. 임의의 두 정점이 인접하지만 체크하는 경우에는 매력적이다.