그래프의 행렬 표현법(Representations of graphs)

그래프의 행렬 표현법(Representations of graphs)

1. 방향성이 없는 그래프와 방향성이 있는 그래프

(1) 방향성이 없는 그래프

[ 출저 : Introduction to algorithms 3/E ]

 

위의 그림을 보면 (a)의 그래프는 5개의 꼭지점과 7개의 선을 가지고 있다.

(a)의 그래프를 인접 리스트로 표현해놓은 것이 (b)의 그림이다.

꼭지점 1의 경우 2와 5에 인접해 있고, 꼭지점 2의 경우 모든 다른 꼭지점과 인접해 있다.

이것을 행렬로 표현하면 (c)와 같다. 행은 현재 꼭지점이 되는 것이고, 열은 다른 꼭지점이라고

생각하면 된다. 즉 위의 그림과 무관하게 아래 행렬을 살펴보자.

	1	2	3	4	5
1	0	0	1	0	0
2	0	0	1	1	0
3	1	1	0	0	0
4	0	1	0	0	1
5	0	0	0	1	0

 

꼭지점 1은 3과 인접해 있고, 꼭지점 3은 1과 2와 인접해 있다는 것을 행렬을 통해 확인할 수 있다.

즉, 1 - 3 - 2 - 4 - 5 의 인접 리스트로 표현할 수 있는 그래프이다.

(2) 방향성이 있는 그래프

[ 출저 : Introduction to algorithms 3/E ]

방향성이 있는 그래프의 경우는 방향성이 없는 그래프보다 더욱 간단하다.

방향성이 없는 그래프의 경우, 1과 2가 인접해 있다면 두 꼭지점 모두에 서로가 인접해 있다고 표시해야한다.

즉, (1, 2) = 1 and (2, 1) = 1. 이 된다.

그러나 방향성이 있는 그래프의 경우에는 1과 2가 인접해 있다고 하더라도, 1이 2를 가르키고 있는

방향을 제시한다면 (1, 2) = 1 and (2, 1) = 0. 이 된다.

2. 가중치가 있는 그래프

[ 출저 : Introduction to algorithms 3/E ]

가중치가 없는 그래프와 가중치가 있는 그래프의 차이는, 인접 유무를 표시하는 수(0 or 1)을

가중치로 표시해주기만 하면 된다. 즉 가중치가 없는 그래프에서 1이 2에 인접해 있다면

(1, 2) = 1 로 표현할 수 있다. 하지만 위의 그림을 보면 1과 2의 사이에는 4의 가중치가 존재한다.

즉, (1, 2) = 4 로 표현하기만 하면된다. 나머지 부분도 그림을 참고하면 쉽게 이해할 것이다.