그래프 표현법(인접 행렬, 인접 리스트)

이번 포스트에서는 그래프의 표현법인 인접 행렬과 인접 리스트에 대해 다루도록 하겠습니다.

 

인접 행렬(Adjacency Matrix)란?

: 그래프의 연결 관계를 2차원 배열로 나타내는 방식입니다. A[u][v]라는 인접 행렬이 있다고 가정하면, 노드 u에서 노드 v로 가는 간선이 있다면 1, 없다면 0으로 표현할 수 있습니다.

 

인접 행렬의 예시 : 

인접 행렬(왼: 무방향성, 오:방향성)

• 무방향성 그래프: A[][]는 대칭 행렬 (이때, A[n(n-1)/2]로 구현 가능)
• 방향성 그래프 : A[][]는 비대칭 행렬
• 장점 : 구현이 쉽다
• 단점: 복잡도 = O(n의 2승)

 

 

 

인접 리스트(Adjacency List)란?

: n개의 정점(vertex)을 각각에 대해 인접한 정점들의 리스트로 만드는 것입니다. 즉, 그래프 G의 각 정점에 대해 한 개의 연결 리스트가 존재한다는 것입니다.

 

인접 리스트의 예시 :

인접 리스트

• 무방향성 : 0은 1, 2, 3이라는 인접 정점을 가지고 있으므로 0->1->2->3이라는 리스트를 가진다.
• 방향성 : 1은 0, 2라는 인접 정점을 가지고 있으므로 1->0->2라는 리스트를 가진다. 반면 2는 인접한 정점이 없으므로 null이라는 리스트를 가진다.
• 장점 : 복잡도 = O(n+e)
• 단점 : 특정 두 점이 연결되었는지 확인하려면 인접행렬에 비해 시간이 오래 걸린다.