[자료구조]그래프의 표현

그래프를 표현하는 방법

인접 행렬

-정점들 사이의 인접관계를 행렬을 이용하여 표현하는 방법

그래프 G=(V,E):n개의 정점을 갖는 (|V(G)|=n>=1) 그래프

→ 인접 행렬 A의 표현

A = (a ij ) : 2차원 n×n 배열.

a ij = 1, if(vi, vj) E(G)에 포함

a ij = 0, if(vi, vj) E(G)에 미포함

-장점: 임의의 두 정점 사이에 간선이 있는지를 쉽게 결정할 수 있고, 정점의 차수(degree)를 쉽게 계산할 수 있다.

-방향 그래프(diagraph)의 경우는  모든 행의 합이 진출차수가 되고, 모든 열의 합이 진입차수가 된다.

 

-단점: 주어진 그래프 내에 간선의 수를 계산하거나 그래프가 연결그래프인지를 결정하는 등의 문제를 해결할 때는 많은 시간을 요구한다.( 행렬의 대각 원소가 모두 0이므로  행렬의 (n^2-n)개의 원소들을 조사해야하기 때문에 적어도 O(n^2)의 시간복잡도가 요구된다.

 

인접 리스트

-정점의 수가 n일 경우, n개의 연결 리스트로 그래프를 표현하는 방법

-리스트 i에는 정점 i와 인접한 모든 정점들이 포함되어있다

-장점: 정점의 차수를 쉽게 구할 수 있다.

(정점의 차수 = 리스트 내의 노드 수)

(n개의 노드를 갖는 그래프에서 간선의 수를 결정하는데 드는 시간 : O(e+n) )

-단점: 방향 그래프를 표현한 경우에는 진입 차수를 결정하기가 힘들다.

(해결-그래프의 역인접리스트(inverse adjency list)를 유지한다.)

 

-가중치간선(weighted edges):그래프의 간선에 가중치가 부여된 간선

---가중치간선의 표현: 인접 행렬의 경우 원소값을 가중치로 두며, 인접 리스트의 경우 가중치 필드를 추가하여 표현