DA :: 인접 다중리스트에 의한 표현

Adjacency Multi-List

• 인접리스트의 단점은 무방향 그래프의 경우 하나의 간선을 나타내는데 2개의 노드가 필요하며 두 개의 다른 리스트에서 표현이 이루어진다는 점이다. 따라서 메모리의 낭비가 발생한다.
• 인접 다중리스트는 하나의 간선에 고유한 식별자를 부여하고 한번만 저장하여 여러 정점이 공유하도록 하는 구조이다. 아래 그림은 인접 다중리스트를 위한 노드의 구조를 나타낸다.

Ei는 간선의 포인터, Vi와 Vj는 Ei에 인접한 정점, Pi와 Pj는 정점 Vi와 Vj에 인접한 간선의 포인터를 나타낸다.

• 위의 그림 (A)와 (B)에서 각 간선에 간선의 식별자를 볼 수 있다. 이러한 식별자를 이용하여 아래의 그림 (C)와 (D)에서는 인접 다중리스트를 보여준다. 예를 들어 그림 (A)에서 정점 2는 간선 E1, E4, E5와 연결되어 있다.
• 이러한 관계를 그림 (C)에서 보여준다. 정점에 인접하는 간선을 선택하는 순서에 따라 하나의 그래프에 대해 여러 형태의 인접 다중리스트가 생성될 수 있다. 이와같은 인접 다중리스트는 무방향 그래프를 표현하기 위한 구조이다. 아래의 그림에서 볼 수 있는 바와 같이 노드의 갯수가 인접리스트에서 보다 적어진 것을 알 수 있다.