이 문서는 Google Cloud Translation API를 사용해 자동 번역되었습니다.
어떤 문서는 원문을 읽는게 나을 수도 있습니다.
그래프는 여러 가지 방법으로 나타낼 수 있지만 인접 목록과 인접 행렬의 두 가지 주요 방법이 있습니다. 이 게시물에서는 이 두 가지 방법을 모두 살펴보고 장단점을 살펴보겠습니다.
인접 목록은 단순히 주어진 정점에 인접한 모든 정점의 목록입니다. 예를 들어 다음 그래프를 고려하십시오.
이 그래프의 인접 목록은 다음과 같습니다.
A: B, C
B: A, C, D
C: A, B, D
D: B, C
보시다시피 각 정점은 인접한 모든 정점과 함께 나열됩니다.
인접 목록은 간단하고 구현하기 쉽다는 장점이 있습니다. 또한 전체 그래프의 모든 가장자리가 아니라 각 정점의 가장자리만 저장하면 되므로 인접 행렬보다 공간을 덜 사용합니다.
인접 목록의 단점은 쿼리 속도가 느릴 수 있다는 것입니다. 예를 들어 정점 A와 D 사이에 가장자리가 있는지 알고 싶다면 A와 D 둘 다에 대한 인접 목록을 살펴보고 둘 중 하나가 다른 하나를 나열하는지 확인해야 합니다. 반대로 인접 행렬을 사용하면 A와 D에 대한 항목만 보고 0이 아닌지 확인할 수 있습니다.
인접 행렬은 각 행과 열이 꼭짓점을 나타내는 행렬(2D 배열)이며 각 행/열 교차점의 값은 두 꼭짓점 사이의 가장자리 가중치입니다. 예를 들어 다음 그래프를 고려하십시오.
이 그래프의 인접 행렬은 다음과 같습니다.
A B C D
A 0 1 1 0
B 1 0 1 1
C 1 1 0 1
D 0 1 1 0
보시다시피 각 행과 열은 정점을 나타내며 각 행/열 교차점의 값은 두 정점 사이의 가장자리 가중치입니다. 두 정점 사이에 가장자리가 없으면 가중치는 0입니다.
인접 행렬은 쿼리가 매우 빠르다는 장점이 있습니다. 예를 들어 정점 A와 D 사이에 가장자리가 있는지 알고 싶다면 A와 D에 대한 항목을 보고 0이 아닌지 확인할 수 있습니다. 대조적으로, 인접 목록을 사용하면 A와 D 둘 중 하나가 다른 것을 나열하는지 확인하기 위해 인접 목록을 모두 살펴봐야 합니다.
인접 행렬의 단점은 인접 목록보다 더 많은 공간을 사용할 수 있다는 것입니다. 예를 들어 위의 그래프에는 16개의 모서리만 있지만 인접 행렬에는 16 * 4 = 64개의 항목이 있습니다. 일반적으로 인접 행렬은 O(V^2) 공간을 사용합니다. 여기서 V는 정점의 수입니다.
인접 목록은 일반적으로 그래프가 희박할 때, 즉 가장자리가 많지 않을 때 사용됩니다. 인접 행렬은 일반적으로 그래프가 조밀할 때, 즉 많은 간선이 있을 때 사용됩니다.
옳고 그른 답은 없으며, 둘 중 하나를 사용하는 것이 종종 가능합니다. 일반적으로 인접 목록은 구현하기가 더 쉽지만 인접 행렬은 쿼리가 더 빠릅니다.