그래프 기초
노드(정점)와 간선(엣지)으로 관계를 표현하는 자료구조. SNS 친구, 도로망, 웹 링크 등 현실 모델링에 필수.
기본 용어
A --- B
| / |
| / |
C --- D
노드(정점): A, B, C, D
간선(엣지): A-B, A-C, B-C, B-D, C-D
차수(degree): A=2, B=3, C=3, D=2
그래프 종류
| 종류 | 설명 | 예시 |
|---|
| 무방향 | A ↔ B | SNS 친구 |
| 방향 | A → B | 팔로우 |
| 가중치 | 간선에 비용 | 도로 거리 |
| 사이클 | 순환 경로 존재 | 순환 참조 |
| DAG | 방향 + 비순환 | 빌드 의존성 |
구현 방법
[인접 행렬]
A B C D
A [ 0, 1, 1, 0 ]
B [ 1, 0, 1, 1 ]
C [ 1, 1, 0, 1 ]
D [ 0, 1, 1, 0 ]
[인접 리스트]
A → [B, C]
B → [A, C, D]
C → [A, B, D]
D → [B, C]
| 구분 | 인접 행렬 | 인접 리스트 |
|---|
| 공간 | O(V²) | O(V+E) |
| 간선 확인 | O(1) | O(degree) |
| 모든 이웃 | O(V) | O(degree) |
| 희소 그래프 | 낭비 | 효율적 |
| 밀집 그래프 | 효율적 | 오버헤드 |
BFS vs DFS
BFS (너비 우선): 가까운 것 먼저
1 → 2, 3 → 4, 5
DFS (깊이 우선): 끝까지 파고듬
1 → 2 → 4 → (돌아옴) → 5 → 3
실무 활용
| 문제 | 알고리즘 |
|---|
| 최단 경로 | BFS, 다익스트라 |
| 사이클 감지 | DFS |
| 위상 정렬 | DFS, 카운트 |
| MST | 크루스칼, 프림 |
| SNS 추천 | BFS (2-hop 친구) |