그래프 표현 방법
그래프 표현이란
그래프를 컴퓨터에서 효율적으로 저장하고 처리하기 위해서는 적절한 자료구조를 선택해야 한다. 그래프 표현 방법은 크게 인접 행렬, 인접 리스트, 간선 리스트 세 가지로 나뉘며, 각 방법은 그래프의 특성과 수행할 연산에 따라 장단점이 있다.
표현 방법 비교
1. 인접 행렬 (Adjacency Matrix)
개념
2차원 배열을 사용하여 그래프를 표현하는 방법으로, matrix[i][j]는 정점 i에서 정점 j로 가는 간선의 정보를 저장한다.
예시
다음과 같은 그래프가 있을 때,
5
0 --- 1
| |
2 | | 3
| |
3 --- 2
4인접 행렬은 다음과 같이 표현할 수 있다.
0 1 2 3
0 [0 5 0 2]
1 [5 0 3 0]
2 [0 3 0 4]
3 [2 0 4 0]특징:
matrix[i][j] = weight: 간선 가중치 저장matrix[i][j] = 0 or ∞: 간선 없음- 무방향 그래프: 대칭 행렬
matrix[i][j] = matrix[j][i] - 방향 그래프: 비대칭 가능
장단점
| 장점 | 단점 |
|---|---|
| 빠른 간선 확인 - O(1) 시간에 연결 여부 확인 - 간선 존재 여부를 즉시 판단 | 높은 공간 복잡도 - O(V²) 메모리 필요 - 정점이 많으면 메모리 낭비 |
| 간단한 구현 - 2차원 배열만으로 표현 - 간선 추가/삭제 O(1) | 희소 그래프 비효율 - 간선이 적어도 V² 공간 필요 - 인접 정점 탐색 O(V) |
2. 인접 리스트 (Adjacency List)
개념
각 정점마다 연결 리스트를 유지하여 인접한 정점들을 저장하는 방법이다.
예시
다음과 같은 그래프가 있을 때,
5
0 --- 1
| |
2 | | 3
| |
3 --- 2
4인접 리스트는 다음과 같이 표현할 수 있다. (정점, 가중치)
0: [(1,5), (3,2)]
1: [(0,5), (2,3)]
2: [(1,3), (3,4)]
3: [(0,2), (2,4)]특징:
- 각 정점마다 (인접정점, 가중치) 쌍을 저장
- 무방향 그래프: 양방향으로 추가
- 방향 그래프: 출발 정점의 리스트에만 추가
장단점
| 장점 | 단점 |
|---|---|
| 공간 효율적 - O(V + E) 메모리 사용 - 실제 간선만 저장 | 간선 확인 느림 - 두 정점 간 연결 확인 O(degree) - 간선 제거 비효율 O(degree) |
| 희소 그래프에 유리 - 간선이 적을 때 메모리 절약 - 인접 정점 탐색 O(degree) | 구현 복잡 - 연결 리스트/동적 배열 필요 - 메모리가 분산되어 캐시 효율 낮음 |
3. 간선 리스트 (Edge List)
개념
모든 간선을 리스트로 저장하는 방법으로, 각 간선은 (u, v) 또는 (u, v, weight) 형태로 표현된다.
예시
다음과 같은 그래프가 있을 때, 간선 리스트는 다음과 같이 표현할 수 있다. (시작정점, 끝정점, 가중치)
5
0 --- 1
| |
2 | | 3
| |
3 --- 2
4간선 리스트는 다음과 같이 표현할 수 있다. (시작정점, 끝정점, 가중치)
[(0, 1, 5), (1, 0, 5), (0, 3, 2), (3, 0, 2), (1, 2, 3), (2, 1, 3), (2, 3, 4), (3, 2, 4)]특징:
- 간선을 (시작정점, 끝정점, 가중치) 형태로 저장
- 무방향 그래프: 양방향 간선을 모두 추가
- 방향 그래프: 한 방향만 추가
장단점
| 장점 | 단점 |
|---|---|
| 간단한 구현 - 배열/리스트로 간단히 표현 - 간선 정렬 용이 | 간선 확인 느림 - 특정 간선 찾기 O(E) - 간선 제거 비효율 O(E) |
| 간선 중심 알고리즘에 최적 - 크루스칼, 벨만-포드 등에 적합 - 공간 효율 O(E) | 그래프 탐색 비효율 - 인접 정점 탐색 어려움 - DFS/BFS에 부적합 |
표현 방법 선택 가이드
연산별 시간 복잡도
| 연산 | 인접 행렬 | 인접 리스트 | 간선 리스트 |
|---|---|---|---|
| 공간 | O(V²) | O(V + E) | O(E) |
| 간선 추가 | O(1) | O(1) | O(1) |
| 간선 제거 | O(1) | O(degree) | O(E) |
| 간선 존재 확인 | O(1) | O(degree) | O(E) |
| 인접 정점 찾기 | O(V) | O(degree) | O(E) |
| 모든 간선 순회 | O(V²) | O(E) | O(E) |
그래프 특성에 따른 선택
| 그래프 특성 | 추천 표현 | 이유 |
|---|---|---|
| 밀집 그래프 (E ≈ V²) | 인접 행렬 | - 공간 차이가 크지 않음 - 간선 확인이 O(1)로 빠름 - 모든 쌍 간선 확인에 유리 |
| 희소 그래프 (E << V²) | 인접 리스트 | - 메모리 절약 (O(V+E)) - 간선 순회 효율적 - 실제 연결된 정점만 저장 |
| 간선 중심 알고리즘 (크루스칼, 벨만-포드 등) | 간선 리스트 | - 간선을 순회하며 처리 - 간선 정렬 용이 - 최소 공간 사용 O(E) |
알고리즘별 적합한 표현
| 알고리즘 | 적합한 표현 | 이유 |
|---|---|---|
| DFS/BFS | 인접 리스트 | 인접 정점 탐색이 빈번 |
| 다익스트라 | 인접 리스트 | 인접 정점 확인 필요 |
| 플로이드-워셜 | 인접 행렬 | 모든 쌍 간선 확인 |
| 크루스칼 | 간선 리스트 | 간선을 가중치 순 정렬 |
| 벨만-포드 | 간선 리스트 | 모든 간선 완화 연산 |
| 프림 | 인접 리스트 | 인접 정점 우선순위 큐 |
실전 선택 기준
주의사항
1. 인접 행렬 사용 시
- 메모리 제한: 정점이 10,000개 이상이면 메모리 초과 가능
- 초기화: 모든 원소를 0 또는 INF로 초기화 필요
- 자기 자신:
matrix[i][i] = 0으로 설정
2. 인접 리스트 사용 시
- 중복 간선 방지: 무방향 그래프에서 양방향 추가 주의
- 가중치 저장: 별도 클래스나 배열 필요
- 정렬: 필요시 인접 정점 리스트 정렬
3. 간선 리스트 사용 시
- 무방향 그래프: 양방향 간선을 모두 추가
- 간선 정렬: 알고리즘에 따라 가중치 순 정렬
- 효율성: 탐색 알고리즘에는 부적합
Last updated on