[자료구조] 그래프(Graph)

 

Graph
 - 선형 자료구조로 표현하기 어려운 다:다 관계를 가지는 원소를 표현

 

G = ( V , E )

vertex 정점: 대상이나 개체　→ V : 정점의 집합
edge 간선: 정점 간의 관계　 → E : 간선의 집합

 

그래프는 정점과 간선으로 정의된다. 계층구조로 이루어진 트리는 선형으로 표현하기 어렵다. 선형으로 표현하기 어려운 자료를 표현하기 위해 그래프가 사용된다.

 

---

 

1. 종류

 

1) 방향으로 분류

① 무방향 그래프, 무향 그래프 (undirected graph)

• 정점을 연결하는 간선의 방향이 없는 그래프
• 방향이 없어 정점 i와 j가 있으면 (i, j) = (j, i)

 

② 방향 그래프, 유향 그래프, 다이 그래프 (directed graph)

• 간선이 방향을 가지고 있는 그래프
• 선후 관계 등을 나타낼 수 있다
• 간선에 화살표를 이용해 표현한다

 

2) 간선에 가중치 부여

가중치 그래프, 네트워크 (weighted graph)

 

3) 그래프 형태로 분류

① 완전 그래프 (complete graph)

• 각 정점이 모든 정점을 연결하여 최대 간선을 가진 그래프
• 무향 그래프에서 최대 간선의 수는 n(n-1)/2
  유향 그래프에서 최대 간선의 수는 n(n-1)

각 정점 n개는 본인을 제외한 모든 정점 (n-1)개와 연결할 수 있다. → n * (n-1)

방향이 없으면 i와 j가 연결된 간선은 (i, j) = (j, i) 를 만족한다. 두 간선은 같은 의미를 가져 중복을 제거하기 위해 2를 나누어 주면 최대 간선의 수가 나온다. 유향 그래프는 방향성을 띄고 있어 서로 연결될 수 있기 때문에 추가로 나누기를 하지 않아도 된다.

 

② 부분 그래프

• 일부 정점이나 간선을 제외하여 만든 그래프

 

---

 

2. 표현 방법

1) 인접 행렬 _ Adjacency matrix

G = (V, E)에서 정점의 개수가 n개라면 n*n 행렬이 필요하다.

 

각 정점 사이에 간선이 존재하면 원소에 1을 넣어준다.

만약 i와 j 사이에 간선이 있는 경우

• 무향 그래프: (i, j), (j, i) 모두 1을 할당
• 유향 그래프: 화살표를 확인하여 방향이 있는 인덱스에 1 할당

간선이 없는 정점은 0을 할당하여 표시한다. 정점 i에서 i로 간선을 놓을 수 없으니, 대각선은 모두 0이어야 한다. 만약 가중치 그래프라면 1대신 가중치값을 할당하여 표시할 수 있다. boolean타입을 이용해 True, False로 표현할 수도 있다.

 

장점: 간선의 존재 여부를 바로 알 수 있다.
단점: n*n 행렬을 생성해야 해서 n²의 공간이 필요하고, 행렬에 원소를 채우는 데 n²의 시간이 걸린다.

 

간선의 밀도가 높은 그래프에서 인접 행렬이 적합하다. 밀도가 낮으면 적은 관계를 위해 많은 공간과 시간이 낭비 된다. 

 

 

2) 인접 리스트 _ Adjacency list

각 정점마다 리스트를 하나씩 생성해 인접한 정점을 연결 리스트로 만든다. 
간선 하나에 노드 2개가 필요하다. 정점에 들어갈 데이터와 다음 노드를 가리킬 공간을 만들어야 한다. 

 

무향 그래프를 리스트로 표현하기 위해 필요한 총 노드의 수는 존재하는 간선의 2배이다. i와 j 사이에 간선이 있으면 정점 i도 j와 연결, 정점 j도 i와 연결한다. 유향 그래프의 경우는 간선 하나에 노드가 하나씩 존재한다.

가중치 그래프를 표현할 때는 가중치를 저장할 공간이 함께 있어야 한다. ⇒ 데이터, 가중치, 다음 노드

 

간선의 수에 비례하는 만큼 공간이 필요하다. 간선의 수가 적을 때 유용하며 간선이 많은 경우, 리스트 생성 시 필요한 오버헤드가 더 필요하다. 리스트를 차례로 확인해 인접 행렬보다 시간이 더 오래 걸린다.

 

 

3) 인접 배열 _ Adjacency array

연결 리스트를 배열로 표현하면 두 정점의 인접 여부를 체크하는 시간을 줄일 수 있다.
배열을 정렬된 형태로 만들어 이진 탐색을 사용할 수 있다. 인접한 정점의 수가 k인 경우, log₂k+1 내로 특정 정점의 존재를 확인할 수 있다.

• 각 정점마다 배열을 따로 할당받아 사용한다.
• 공간을 깔끔하게 사용하기 위해 하나의 배열로 사용한다.

 

1. 각 인접 배열의 크기를 더해 전체 배열 크기만큼 배열을 생성한다.
2. 각 정점의 헤더에 배열이 끝나는 자리를 표시한다.

< 예시 >

1번에 3개, 2번에 1개, 3번에 2개, 4번에 1개→ 3+1+2+1 = 7 ⇒ arr[7]

1: 2　→ arr[0], arr[1], arr[2]
2: 3　→ arr[3]
3: 5　→ arr[4], arr[5]
4: 6　→ arr[6]

 

인접 리스트처럼 간선 수에 비례하는 공간을 사용하고, 검색 시간을 줄여 실용적으로 사용할 수 있다.