인접 리스트와 그래프의 행렬 표현
사라 첸
⚡ 스마트 요약
그래프의 인접 리스트 및 행렬 표현은 정점과 간선을 메모리에 저장하여 알고리즘이 네트워크를 탐색할 수 있도록 합니다. 인접 리스트는 각 정점마다 연결 리스트를 사용하는 반면, 인접 행렬은 정사각형 2차원 격자를 사용합니다.
겉모습은 달라도 다들 그래프의 종류 비슷한 방식으로 표현할 수 있습니다. 그래프 표현에는 일반적으로 두 가지 유형이 있습니다.
- 인접 매트릭스
- 인접 목록
인접 목록
인접 리스트는 연결 리스트로 구성됩니다. 각 정점은 배열의 인덱스로 간주되며, 각 요소는 연결 리스트를 나타냅니다. 이 연결 리스트에는 해당 인덱스 정점과 간선을 공유하는 정점들이 저장됩니다.
다음은 인접 리스트의 예입니다.
정점의 개수가 V개이고 간선의 개수가 E개인 그래프가 있다고 할 때, 인접 리스트의 공간 복잡도는 다음과 같습니다. O(V + E)이는 모든 가능한 정점 쌍이 아니라 실제 간선의 수에 비례하여 확장됩니다.
최악의 경우 공간 복잡도는 다음과 같습니다. O(V²) 주어진 그래프가 완전 그래프라면, 모든 정점이 다른 모든 정점과 연결되어 있기 때문입니다.
인접 매트릭스
인접 행렬은 2차원 배열로 구성됩니다. 정점이 V개인 그래프의 경우, 행렬의 크기는 다음과 같습니다. V × V.
말하다 matrix[i][j] = 5이는 노드 i와 노드 j 사이에 가중치가 5인 간선이 있다는 것을 의미합니다.
다음 그래프와 그 인접행렬을 살펴보겠습니다.
우리는 2D 배열 다음 단계를 사용하여:
단계 1) 정점 A는 정점 B와 직접 연결되어 있으며, 가중치는 5입니다. 따라서 A행 B열의 해당 칸에는 5가 채워집니다. A행의 나머지 칸에는 0이 채워집니다.
단계 2) 정점 B는 정점 C와 직접 간선을 가지고 있으며, 간선의 가중치는 4입니다. 따라서 B행 C열의 해당 칸에는 4가 채워집니다. B는 다른 노드로 나가는 간선이 없으므로 B행의 나머지 칸에는 0이 채워집니다.
단계 3) 정점 C는 다른 어떤 정점과도 직접적인 간선이 없습니다. 따라서 C행은 0으로 채워집니다.
단계 4) 정점 D는 A 및 C와 방향 간선을 가지고 있습니다.
- D행 A열의 셀에는 7이라는 값이 들어갑니다. D행 C열의 셀에는 2라는 값이 들어갑니다.
- D행의 나머지 셀은 XNUMX으로 채워집니다.
단계 5) 정점 E는 정점 B 및 D와 방향 간선을 가지고 있습니다. E행 B열의 셀에는 6의 값이, E행 D열의 셀에는 3의 값이 저장됩니다. E행의 나머지 셀은 모두 0으로 채워집니다.
주의할 점은 다음과 같습니다.
- 인접행렬의 주대각선이 0일 때, 그래프에는 자체 루프가 없습니다.
- (a, b)와 (b, a) 위치의 셀 값이 다르면 해당 그래프는 방향 그래프입니다. 그렇지 않으면 무방향 그래프입니다.
- 어떤 셀의 값이 1보다 크면 해당 그래프는 가중 그래프입니다.
인접 행렬의 가장 큰 문제는 정사각형 형태의 메모리 공간을 필요로 한다는 점입니다. 존재하지 않는 간선조차도 메모리 공간을 할당합니다.
예를 들어, 노드가 100개인 그래프가 있다면 이를 저장하려면 10,000개의 셀이 필요합니다. 램그래프의 간선 수가 적을수록 이처럼 큰 메모리를 할당하는 것은 낭비일 수 있습니다. 따라서 인접 행렬을 사용하는 공간 복잡도는 다음과 같습니다. O(N²)여기서 N은 그래프의 노드 수입니다.
인접 리스트와 인접 행렬의 차이점
표현 방식을 선택하기 전에 실제 그래프 워크로드에서 가장 많이 사용되는 연산들을 기준으로 두 모델을 나란히 비교해 보는 것이 도움이 됩니다.
| Opera기 | 인접 매트릭스 | 인접 목록 |
|---|---|---|
| 공간 복잡성 | O(V²) | O(V + E) |
| 정점을 추가합니다 | O(V²) | O (1) |
| 엣지를 더하세요 | O (1) | O (1) |
| 모서리를 제거하세요 | O (1) | 오(E) |
| 간선 (i, j)이 존재하는지 확인합니다. | O (1) | O(i의 차수) |
| i의 이웃들을 순회합니다. | O (V) | O(i의 차수) |
| 가장 좋은 | 밀집된 그래프, 빈번한 엣지 쿼리 | 희소 그래프, 순회 작업이 많은 작업 |
요약하자면, 인접 행렬은 상수 시간 에지 검색에서 우위를 점하는 반면, 인접 리스트는 메모리 사용량과 이웃 반복 횟수에서 우위를 점합니다. 이것이 바로 BFS, DFS, 다익스트라 알고리즘이 일반적으로 인접 리스트와 함께 사용되는 이유입니다.
그래프 표현의 장점과 단점
각 표현 방식에는 장단점이 있습니다. 두 모델의 장점과 단점을 모두 알면 해결하려는 문제에 가장 적합한 모델을 선택하는 데 도움이 됩니다.
인접행렬의 장점:
- 임의의 두 정점 사이의 에지 존재 여부를 상수 시간 O(1) 쿼리합니다.
- 고정 인덱싱을 사용하면 플로이드-워셜 알고리즘이나 전이 폐쇄와 같은 행렬 기반 알고리즘을 쉽게 구현할 수 있습니다.
- 가중치가 부여된 모서리는 단일 행렬 셀에 자연스럽게 들어맞습니다.
인접 행렬의 단점:
- 그래프가 희소할 경우 O(V²) 메모리를 낭비합니다.
- 새로운 꼭짓점을 추가하려면 전체 행렬의 크기를 조정해야 합니다.
- 단일 정점의 이웃을 순회하는 데는 정점에 간선이 몇 개만 있는 경우에도 O(V) 시간이 걸립니다.
인접 리스트의 장점:
- 이 함수는 O(V + E)의 메모리만 사용하는데, 이는 희소 그래프의 실제 에지 수와 거의 같습니다.
- 새로운 정점이나 간선을 추가하는 데는 O(1)이 소요됩니다.
- BFS 및 DFS와 같은 순회 알고리즘은 이웃을 O(차수)의 시간 복잡도로 순회하므로 전체 실행 시간은 O(V + E)입니다.
인접 리스트의 단점:
- 특정 간선이 존재하는지 확인하는 데는 O(1)이 아닌 O(차수) 시간이 걸립니다.
- 연결 리스트가 메모리 전체에 분산되어 있기 때문에 캐시 지역성이 약해집니다.
- 가중치가 부여된 에지에는 보조 필드 또는 쌍 목록이 필요하므로 데이터 구조가 약간 복잡해집니다.
인접 리스트와 인접 행렬은 언제 사용해야 할까요?
그래프 표현 방식 선택은 그래프의 밀도와 가장 자주 실행하는 연산에 따라 달라집니다. 이 간편 가이드를 활용하여 적절한 구조를 선택하세요.
- 인접 행렬을 선호합니다. 그래프가 밀집되어 있을 때(E가 V²에 가까울 때), 간선이 거의 바뀌지 않을 때, 그리고 알고리즘이 "i와 j 사이에 간선이 있습니까?"라고 여러 번 물을 때입니다.
- 인접 목록을 선호합니다. 그래프가 희소할 때(E가 V²보다 훨씬 작을 때), 실행 중에 정점 또는 간선 집합이 증가할 때, 그리고 BFS, DFS 또는 기타 알고리즘으로 그래프를 탐색할 때 다익스트라의 최단 경로 알고리즘.
- 혼합 모델을 선호합니다 (인접 목록과 간선의 해시 집합) 빠른 이웃 반복과 O(1) 간선 쿼리가 모두 필요할 때 추가 메모리가 필요합니다.
NetworkX나 igraph 같은 최신 그래프 라이브러리는 대부분의 실제 그래프(소셜 네트워크, 로드맵, 웹 페이지, 패키지 종속성 등)가 희소하고 탐색이 많이 필요하기 때문에 기본적으로 인접 리스트를 사용합니다.
