자료구조 (Data Structure) (6) - 그래프 표현 방식 : 인접 리스트 (Adjacency List)

그래프의 표현 방식 2번째인 인접 리스트 (adjacency list) 에 대해서 알아보자. 인접 리스트 방식에서는 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결해서 저장한다. 

위의 그림과 같이 노드0에 노드1, 노드2, 노드3이 연결되어 있다는 것을 표현했고 같은 방식으로 노드1, 노드2, 노드3에 연결된 노드들을 차례대로 저장하였다. 위의 그림은 C언어에서의 인접 리스트 표현 방식인데 C에서는 배열에 포인터를 넣어서 연결된 노드들을 가리키게 된다. 파이썬에서는 인접 행렬과 동일하게 2차원 리스트로 인접 리스트를 표현할 수 있다.

가중치가 있는 그래프에서의 인접 리스트 표현 방식은 아래와 같다.

위의 그래프를 인접 리스트로 표현하는 소스코드는 아래와 같다.

---

인접 행렬과 인접 리스트의 차이점은 무엇일까.

먼저 메모리 측면에서 보면 인접 행렬은 모든 노드의 관계에 대해서 저장하기 때문에 불필요한 메모리를 많이 차지하게 된다. 반면에 인접 리스트는 연결되어 있는 노드만 나타내기 때문에 더욱 적은 메모리만을 차지하게 되는 것이다.

다음으로 속도 측면에서 살펴보면 인접 행렬은 해당하는 행과 열에 접근하면 정보를 알 수 있기 때문에 비교적 빠른 속도를 자랑한다. 그러나 인접 리스트는 해당 노드에 접근해서 연결된 노드들을 모두 확인해야 하기 때문에 속도가 느린것이다.

이렇듯 인접 행렬과 인접 리스트는 분명한 차이점과 장단점을 가지고 있다. 따라서 문제를 잘 해석하고 어떠한 표현 방식으로 그래프를 표현해서 문제를 풀 것인가를 정하는 것이 중요하다고 할 수 있다.