2025-08-31 11:52
Tags: 자료구조
간선 (Edge, Arc, Link)
-
방향성
- 무방향 간선(양방향)
- 방향 간선(단방향)
-
가중치
- 비가중치 간선: 모든 관계 중요도 동일, 단순 연결 여부
- 가중치 간선: 간선에 숫자값 부여 → 관계의 특성 나타냄
| 구현 방식 | 간선 (u, v)의 표현 | 특징 |
|---|---|---|
| 인접 행렬 | matrix[u][v] = 1 (비가중치) 또는 matrix[u][v] = weight (가중치) | 간선의 존재 여부나 가중치를 O(1)으로 빠르게 조회할 수 있습니다. |
| 인접 리스트 | list[u]에 v를 추가합니다. (가중치는 (v, weight) 쌍으로 추가) | 특정 노드 u에 연결된 모든 간선을 순회하는 데 효율적입니다. O(degree(u)) |
- 인접 행렬:
matrix[A][B] = 10,matrix[B][A] = 10(무방향일 경우) - 인접 리스트: A의 리스트에
(B, 10)추가, B의 리스트에(A, 10)추가