정점(vertex, 노드)과 정점들을 잇는 간선(edge)으로 이루어진 자료구조. 트리도 그래프의 한 종류다. SNS 친구 관계, 지도와 경로, 웹 페이지 링크, 추천 시스템, 패키지 의존성처럼 "무엇과 무엇이 연결돼 있다"는 모든 것을 표현한다. 이 지식 맵도 노트를 정점, 링크를 간선으로 한 그래프다.
종류
- 무방향 / 방향(Undirected / Directed): 친구 관계(양쪽) / 팔로우(한쪽)
- 가중치 없음 / 가중치 있음(Unweighted / Weighted): 간선에 거리·비용이 붙으면 가중 그래프다(다익스트라 알고리즘)
- 두 정점이 간선으로 이어지면 "인접하다(Adjacent)"고 한다
표현 방법
| 인접 리스트(Adjacency List) | 인접 행렬(Adjacency Matrix) | |
|---|---|---|
| 모양 | 정점마다 이웃 목록 | 정점 수 × 정점 수 표 |
| 공간 | O(V + E) | O(V²) |
| 두 정점이 이웃인가 | 이웃 목록을 훑는다 | O(1) |
| 이웃 전체 순회 | 빠르다 | 한 행 전체를 본다 |
const graph: Record<string, string[]> = {
A: ['B', 'C'],
B: ['A', 'D'],
C: ['A', 'D'],
D: ['B', 'C'],
}실제 그래프는 대부분 간선이 드문(희소한, Sparse) 거대한 그래프라서 인접 리스트를 주로 쓴다.
순회
모든 정점을 방문하는 방법은 깊게 먼저 가는 깊이 우선 탐색 (DFS)와 가까운 곳부터 넓게 가는 너비 우선 탐색 (BFS)가 있다. 방문한 정점을 기록해 순환에 빠지지 않게 하는 것이 트리 순회(트리 순회)와 다른 점이다. 의존 관계 그래프에서 순환을 찾고 순서를 정하는 일은 번들러와 모노레포 빌드 도구의 핵심 작업이다.