그래프(Graph) 자료구조 구현방법 2가지

1. Adjacency Matrix

 

그래프의 각 노드(혹은 vertex)들을 x축, y축에 나열하고 x,y의 교점에 두 노드의 연결 여부를 표시한다.

 

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

장점

a, b의 연결 여부를 확인할 때 O(1) 밖에 걸리지 않는다.

a, b의 연결 여부를 변경할 때 O(1) 밖에 걸리지 않는다.

 

단점

O(V^2)의 공간을 차지한다 (V = Vertex)

노드를 추가 혹은 제거할 때 O(V^2)만큼 소요된다.

 

 

2. Adjacency List

그래프의 각 노드별로 그 노드와 연결되어있는 다른 노드들의 정보가 담긴 리스트를 만들고, 이 리스트들을 하나로 모은다.

*노드 목록 구현은 리스트/다이나믹 어레이(vector)도 사용 가능하고, 링크드 리스트도 사용 가능하다.

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

장점

공간을 O(V * E)만큼 차지한다. 최악의 경우 O(V^2)만큼 차지한다. (V,E = Vertex, Edge) 

새로운 노드를 추가하는게 간단하다.

 

단점

두 노드의 연결여부를 확인하는 데 시간이 O(V)만큼 소요된다.