백과

그래프를 기억영역 안에 표현하는 대표적인 방법의 하나. 리스트 표현에 따르면 그래프의 검색의 번거로움 없이 행하여지는 경우가 많고, 또한 기억영역도 그래프의 크기 m+n(m은 가지수, n은 노드수)에 비례함으로써 끝난다. 대규모이고 조밀하지 않은 그래프(가지수가 상대적으로 적은 그래프)를 표현하는데 특히 편하다.

이 점은 그래프의 표현이 지니는 또 하나의 대표적인 방법으로, 행렬표현과 대조적이다. 예를 들면 인접행렬에서는 n²에 비례하는 기억영역이 필요하다. 어느 쪽 표현이 유리한가는, 응용에 따라 다르지만, 그래프의 고속 알고리즘에는 리스트 표현을 전제로 한 것이 매우 많다.

다음은 가장 간단하며 많이 사용되고 있는 리스트 표현에 대해 설명한다. 유향 그래프를 표현하려면 배열 A[1..n], X[1..m], Y[1..m]를 준비한다. 우선 노드 i에 대해, i에서 나오는 가지의 집합을 임의의 순서로 1열로 늘어놓고, 이것을 1방향 리스트로 표현한다. 거기에는 이 열의 선두 가지의 번호를 A[i]에 넣어, 그 열 중에 있는 가지의 번호 k에 대하여, 그 다음 가지의 번호를 X[k]에 넣는다. 또한 Y[k]에는 가지 k가 들어가는 노드의 번호를 넣는다.

이와 같은 표현에 따라, 예를 들면 깊이 우선검색의 절차가 번거로움 없이 실현된다. 각 가지에 대해서는 그 가지가 나오는 노드까지 직접 알고자 할 경우의 응용에는 위의 Y와 똑같은 배열을 하나 더 추가한다. 또한 각 노드에 대해서 그 노드에 들어가는 가지의 집합을 직접 알고자 할 경우의 응용에는 위의 A, X와 같은 배열을 각각 추가한다.

더 나아가서 노드나 가지의 삽입이나 삭제가 동적으로 실행되게 하려는 응용에는, 위의 가지의 집합을 쌍방향 리스트로 표현하면 편리하다. 또한 무향 그래프는 각 가지가 2개의 유향 가지라 보고 유향 그래프로서 표현하면 좋다(예를 들면 2개의 가지는 본래의 가지 번호를 2배하여 0이나 1을 보탬으로써 표현한다).