Graph 표현 방법 Adjacency Matrix (C 언어)

figure 1. G(V,E)

G(V,E)를 컴퓨터 상에서 표현하는 방법은 크게 두 가지가 있습니다.

Adjacency Matrix 와 Adjacency List.

 

Adjacency는 보통 줄여서 Adj 라고 적기도 하는데 인접이라는 의미를 가지고 있어서

근처에 있는 것을 표현한다고 생각하면 됩니다.

 

1. Adjacency Matrix

int Matrix[4][4] 

Matrix[i][j] 는 (i,j) edge가 있을 경우 1로, 없을 경우 0으로 값을 가집니다.

vertex	1	2	3	4
1	0	1	0	1
2	1	0	0	1
3	0	0	0	1
4	1	1	1	0

빨간색으로 표시된 부분은 꼭지점 4와 나머지 1,2,3과의 관계를 나타내고 있습니다.

만일 4와 2를 잇는 모서리가 있는 지 확인하고 싶다면 Matrix[4][2] 를 확인하면 되겠네요!

 

2. Adjacency List

Adjacency List는 list[i]에 i와 인접한 꼭지점을 포함시키는 방법입니다.

figure 1. G(V,E)

Figure 2. Adj List

참조. C로쓴 자료구조