6-2. 그래프의 표현(인접 행렬, 인접 리스트, 인접 다중 리스트)

2018. 7. 22. 15:53자료구조

반응형

1. 그래프의 표현

그래프를 표현하는 방법은 여러가지가 있지만 그 중 대표적인 방법이 인접행렬(adjacency matrix), 인접 리스트(adjacency list), 인접 다중 리스트(adjacency multi list)이다. 이때 어떤 표현 방법을 선택하느냐 하는 것은 그래프에 수행시키려는 연산과 이용하려는 응용에 달려 있다고 하겠다.


1) 인접 행렬(adjacency matrix)

그래프 G = (V, E)를 n >= 1(n은 정점이 수)의 정점의 가진 그래프라고 하였을 때 그래프 G에 대한 인접행렬의 크기는 n * n이며 a[n, n] 크기의 2차원 배열로 표현됩니다. 이때 a[n, n]에서 a[i, j] ∈ E(G)라면 1값을 아니라면 0의 값을 가지게 된다. 


아래 그림은 그래프와 그에 해당하는 인접행렬의 표현이다.  그림 a의 그래프는 무방향 그래프의 인접행렬의 표현이다.  무방향 그래프에 인접행렬은 간선간의 특성상 대칭이 된다. 그 이유는 a[i, j] ∈ E(G)라면 반드시 a[j, i] ∈ E(G)이기 때문이다. 그렇기 때문에 인접행렬 표현에 필요한 공간의 크기는 n^2이지만 무방향 인접행렬의 경우는 상위나 하위만 저장하여서 공간의 절약이 가능하다.  그림 b의 그래프는 방향 그래프의 인접행렬의 표현이다.



인접행렬의 표현방식에서 진입 차수와 진출차수는 a[i, j] ∈ E(G)의 경우에 i 행의 합을 구하면 진출 차수이고 i 열의 합을 구하면 진입 차수이다.



2) 인접 리스트(adjacency list)

인접 리스트로 그래프를 표현하는 방법은 n개의 정점을 각각에 대해 인접한 정점들의 리스트로 만드는 것이다. 그러기 위해서는 아래 그림과 같이 리스트의 노드 구조를 정점(vertex)필드와 주소(link)필드로 구성하여야 한다. 그래야만 어떤 정점 i에 대한 인접 리스트에 정점 i와 인접한 정점들을 나타내는 노드들을 포함시키게 할 수 있다. 아래 그림은 그래프를 인접 리스트로 나타낸 것이다. 여기서 유의할 점은 각 정점의 리스트는 헤더 노드를 가지고 있고 리스트 헤더들은 배열을 이용하여 노드 번호를 오름 차순으로 정렬되어 있다. 이렇게 하면 특정 정점에 대한 인접 리스트를  빠르게 접근 할 수 있다. 그러나 리스트 내의 노드 순서는 그 이외에 다른 특별한 의미를 갖지 않는다. 





아래와 같은 방식을 사용할 때에는 정점 n개와 간선 e개를 가진 무방향 그래프의 경우 n개의 해더 노드와 2e개의 리스트 노드가 필요하게 된다.  그리고 각 리스트 노드는 link 필드를 가지게 된다. 그러나 포인터를 사용하지 않고 인접 리스트의 노드를 순차적으로 묶어서 저장하는 방법도 있다. 이 경우 배열 vertex[]를 사용한다면 배열이 크기는 n +2e +1이된다. 이는 link의 공간이 필요없기 때문에 공간의 사용을 줄일 수 있습니다.


아래 그림은 위 <a>그림의 그래프를 배열의 순차 표현으로 나타내고 있습니다. 

  • 정점이 4개, 간선이 5개이기 때문에 n + 2e +1로 개산하면 배열의 크기는 15가 됩니다. 

  • 배열의 0~n-1까지 자리는 각 정점별 인접 리스트의 시작 위치를 나타냅니다. 

  • 배열의 n번째 자리는 배열의 크기를 나타냅니다. 여기서 배열의 크기는 15입니다.

  • 이후 n+1 ~ n+2e +1 -1 자리까지는 각 정점의 인접 리스트를 담고 있습니다. 예로 배열 [7], [8], [9]에는 1번 정점의 인접 리스트입니다.



3) 인접 다중 리스트(adjacency multi list)

무방향 인접 리스트의 표현에서 각 간선은 (i, j)는 실제로 i정점과 j정점 두 개의 인접 리스트를 포함하게 된다. 즉 하나의 간선은 두개의 노드의 인접 리스트를 표현 할 수 있습니다. 이러한 점을 사용해서 만든것이 다중 리스트이다. 즉 다중 리스트란 노드들이 여러 리스트들이 공용하는 리스트를 말합니다. 내용이 어려워서 아래 그림을 보면서 설명하겠습니다.



위 그림은 그림의 <a> 그래프를 인접 다중 리스트로 나타낸 것입니다.  우선 간선을 표현하는 노드 리스트를 보시면 M은 마크 비트로 이 간선이 이미 검사되었는지 여부를 확인합니다. i, j는 각 간선에 부속된 정점 입니다. i-link, j-link는 각 정점의 인접 리스트의 링크를 나타냅니다.


정점 0에 대한 인접리스트는 다음과 같이 식별하는 법은 다음과 같습니다. 정점 0은 최초 E0로 이동하고 E0리스트의 정점 0의 인접 리스트의 링크와 연결된 E1으로 이동하게 됩니다. 다시한번 E1리스트의 정점 0의 인접리스트 링크를 확인하니 null이기 때무에 리스트가 끝나게 됩니다. 


위 그래프의 모든 정점의 인접 리스트를 식별하면 다음과 같습니다.

  • 정점0 : E0 → E1
  • 정점1 : E0 → E2 → E3
  • 정점2 : E2 → E4
  • 정점3 : E1 → E3 → E4


반응형
  • 프로필사진
    ㅇㅇ2018.12.11 18:06

    인접다중리스트에 정점1: E0->E2->E3가 맞는거 같아요!!

    • 프로필사진
      Favicon of https://kingpodo.tistory.com BlogIcon KimHyoSeop2018.12.15 19:08 신고

      제가 쓴 글을 끝까지 봐주셔서 감사합니다. 말씀해주신 내용이 맞네요 수정하였습니다. 요즘에는 글을 못올리고 있지만 조만간 다시 올리려고합니다. 앞으로도 많이 봐주시고 피드백 남겨주시면 감사합니다.

  • 프로필사진

    내용 잘봤습니다 !!
    혹시 이미지를 제 블로그에 사용해도 괜찮을까요 ? 출처는 남기겠습니다 !

  • 프로필사진
    인접행렬2021.03.22 06:35

    인접행렬 이미지에 [2][3]이 1이면 [3][2]도 1이 되어야 하는데요 잘못 기재된듯 합니다.