목차11개 항목
출처와 참고
용어 정리와 그래프·트리 비교는 팔만코딩경(42Seoul 커뮤니티 위키)의 「[자료구조] 그래프(Graph) 개념 정리」, 「그래프 자료구조」를 바탕으로 보강했다. 딕셔너리 인접 리스트, 탐색 기법의 빈도, 「놓치기 쉬운 것」은 Tech Interview Handbook의 「Graph cheatsheet」를 바탕으로 보강했다. 사이클 없는 그래프와 트리의 차이, 밀집·중복 간선의 표현은 fru1tworld/cs-basic 모의 면접 질문 목록의 「자료구조」 질문이 묻는 개념으로 보강했다.
그래프(Graph)는 정점(vertex, node)과 정점을 잇는 간선(edge)으로 이루어진 자료구조다. 간선에 방향이 있으면 방향(단방향) 그래프, 없으면 무방향(양방향) 그래프다.
그래프의 종류
- 완전 그래프(Complete Graph): 모든 정점이 다른 모든 정점과 연결되어 간선 수가 최대인 그래프. 정점이 n개일 때 무방향 그래프는 n(n-1)/2개, 방향 그래프는 두 정점 사이에 방향이 다른 간선 두 개를 둘 수 있으므로 n(n-1)개의 간선을 가진다. 예: 정점 4개인 무방향 완전 그래프의 간선은 6개.
- 부분 그래프(Subgraph): 원래 그래프에서 일부 정점이나 간선을 빼서 만든 그래프
- 가중 그래프(Weighted Graph): 간선마다 비용(가중치)이 붙은 그래프. 네트워크라고도 한다. 최단 경로 문제의 대상이다.
- 연결 그래프(Connected Graph): 무방향 그래프에서 모든 정점 쌍 사이에 경로가 있는 그래프. 경로가 없는 쌍이 있으면 비연결 그래프이고, 서로 이어진 덩어리 각각을 연결 요소(connected component) 라 한다.
- 이 밖에 사이클이 없는 방향 그래프(DAG), 사이클 없이 모든 정점이 연결된 트리 등이 자주 나온다.
용어
| 용어 | 뜻 |
|---|---|
| 인접(adjacent) | 간선 하나로 바로 이어진 두 정점의 관계 |
| 차수(degree) | 무방향 그래프에서 한 정점에 붙은 간선 수. 모든 차수의 합 = 간선 수 × 2 |
| 진입 차수·진출 차수 | 방향 그래프에서 들어오는(in-degree)·나가는(out-degree) 간선 수. 위상 정렬은 진입 차수 0인 정점부터 꺼낸다 |
| 경로(path)·경로 길이 | 간선으로 이어진 정점의 나열과, 그 경로에 쓰인 간선 수 |
| 단순 경로(simple path) | 같은 정점을 두 번 지나지 않는 경로 |
| 사이클(cycle) | 시작과 끝이 같은 단순 경로. 사이클이 없으면 비순환(acyclic) 그래프 |
그래프와 트리
트리는 그래프의 특수한 경우다. 사이클이 없는 연결 그래프가 트리이고, 정점이 n개면 간선은 정확히 n-1개다.
| 그래프 | 트리 | |
|---|---|---|
| 사이클·자기 루프 | 있을 수 있다 | 없다 |
| 두 정점 사이 경로 | 여러 개일 수 있다 | 정확히 하나 |
| 루트·부모-자식 | 개념이 없다 | 루트 하나, 루트 외의 노드는 부모가 하나 |
| 간선 수 | 정해져 있지 않다 | n - 1 |
| 모델 | 네트워크 | 계층 |
| 순회 | BFS, DFS (방문 체크 필수) | 전위·중위·후위·레벨 순회 |
사이클이 없다고 모두 트리는 아니다. 트리는 「사이클 없음」과 「연결됨」을 함께 만족해야 한다.
| 그래프 | 트리인가 | 이유 |
|---|---|---|
| 사이클 없는 무방향 그래프가 여러 덩어리 | 아니다. 숲(forest) 이다 | 연결되지 않았다. 덩어리 하나하나가 트리이고, 간선 수는 n - (덩어리 수)다 |
DAG A→B, A→C, B→D, C→D | 아니다 | 방향 사이클은 없지만 D의 부모가 둘이고, 방향을 지우면 A-B-D-C-A 사이클이 생긴다 |
| 사이클 없고 연결된 무방향 그래프 | 트리다 | 정의 그대로 |
정점이 n개인 무방향 그래프에서 「연결됨」, 「사이클 없음」, 「간선 n-1개」 중 두 가지가 성립하면 나머지 하나도 성립해 트리다. 그래서 간선 목록이 트리인지는 간선 수가 n-1인지 보고, Union-Find로 사이클이 없는지(또는 BFS로 연결됐는지) 하나만 더 확인하면 된다.
트리의 용어와 순회는 트리와 이진 탐색 트리에 정리했다.
그래프 표현: 간선 정보를 어떻게 저장할까
인접 행렬 (Adjacency Matrix): 모든 관계를 저장
V×V 2차원 배열에서 matrix[i][j]에 i → j 간선이 있으면 1(또는 가중치), 없으면 0(또는 무한대)을 둔다.
INF = float('inf')
matrix = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 0],
]인접 리스트 (Adjacency List): 연결된 것만 저장
정점마다 연결된 정점(과 가중치)의 목록을 둔다.
n, m = 3, 2
graph = [[] for _ in range(n)]
edges = [(0, 1, 7), (0, 2, 5)]
for a, b, cost in edges:
graph[a].append((b, cost))
graph[b].append((a, cost)) # 무방향이면 양쪽에 추가비교
| 인접 행렬 | 인접 리스트 | |
|---|---|---|
| 메모리 | O(V²): 간선이 적어도 V² 칸 필요 | O(V + E): 실제 간선만 저장 |
| 두 정점이 연결됐는지 확인 | O(1) | O(해당 정점의 차수) |
| 한 정점의 이웃 모두 순회 | O(V) | O(차수) |
| 전체 탐색(BFS/DFS) | O(V²) | O(V + E) |
| 어울리는 경우 | 정점 수가 적고 간선이 빽빽한 그래프, 플로이드-워셜 | 정점이 많고 간선이 드문 그래프(대부분의 문제) |
간선이 얼마나 많아야 「빽빽하다」고 보나. 같은 쌍을 잇는 간선이 하나뿐인 단순 그래프는 간선이 최대 V(V-1)/2개(무방향)라, E가 V²에 가까우면 인접 리스트도 O(V²) 공간이 들고 행렬과 차이가 없어진다. 그러면 O(1) 연결 확인과 단순한 구조를 가진 행렬이 낫다. 간선이 V³개처럼 V²보다 많이 주어진다면 같은 쌍을 잇는 중복 간선(multi-edge) 이 있다는 뜻이다. 최단 경로·MST처럼 쌍마다 가장 싼 간선만 의미 있는 문제는 입력을 읽으며 matrix[a][b] = min(matrix[a][b], cost)로 접어 O(V²) 공간에 담는다. 인접 리스트에 V³개를 그대로 담으면 메모리와 순회 비용이 모두 V³이다.
정점이 10만 개라면 인접 행렬은 100억 칸이라 메모리 초과가 난다. 코딩 테스트에서는 인접 리스트가 기본이고, 정점이 수백 개 이하이거나 연결 여부를 자주 물을 때 인접 행렬을 쓴다. 정점이 문자열이거나 번호가 듬성듬성하면 딕셔너리 인접 리스트(defaultdict(set), 가중치가 있으면 딕셔너리의 딕셔너리)가 가장 간단하다. 간선 목록으로 주어지면 먼저 이런 구조로 바꾼 뒤 탐색한다.
그래프 탐색 기법
| 기법 | 핵심 자료구조 | 용도 |
|---|---|---|
| BFS | 큐 | 가중치 없는 그래프의 최단 거리 |
| DFS | 스택/재귀 | 완전 탐색, 연결 요소, 백트래킹 |
| 다익스트라 | 우선순위 큐 | 음이 아닌 가중치 그래프의 최단 거리 |
| Union-Find | parent 배열 | 연결 여부, 무방향 사이클 판별 |
| 위상 정렬 | 진입 차수 + 큐 | 방향 비순환 그래프의 의존 순서, 방향 사이클 판별 |
BFS·DFS·위상 정렬은 모두 O(V + E)다. 가중치·음수 간선·전체 쌍 여부에 따라 최단 경로 알고리즘을 고르는 기준은 최단 경로 알고리즘 고르기에 있다. 면접에서는 BFS·DFS가 대부분이고 위상 정렬·다익스트라가 가끔 나온다. 벨만-포드, 플로이드-워셜, 최소 신장 트리는 드물다.
그래프 문제의 두 가지 유형
- 격자(미로) 탐색 유형: 2차원 지도가 주어지고 현재 좌표에서 상하좌우로 이동하며 길을 찾는다. 지도가 곧 그래프이므로 따로 인접 리스트를 만들지 않고, 행렬을 지도 그림 그대로 보면서 방향 배열
(dx, dy)로 이웃을 계산하는 편이 쉽다. - 정점 이동 유형: "a와 b가 연결되어 있다" 같은 간선 정보가 주어진다. 이를 바탕으로 인접 리스트(또는 행렬)를 만든 뒤, 방문 여부를 boolean 배열로 체크하며 탐색한다.
놓치기 쉬운 것
- 트리처럼 보여도 그래프일 수 있다. 사이클이 있을 수 있으면 방문 집합 없이 재귀하면 무한 루프에 빠진다. 각 정점을 한 번만 방문하는지 확인한다.
- 연결되지 않은 그래프는 한 정점에서 시작한 탐색으로 다 못 본다. 모든 정점을 돌며 미방문 정점에서 탐색을 새로 시작한다.
- 격자에서는 이웃 좌표가 범위 안인지와 이미 방문했는지를 매번 함께 본다.
- 빈 그래프, 정점 1~2개, 자기 루프와 중복 간선도 경계 사례다.
핵심 정리
- 그래프 = 정점 + 간선, 방향/무방향, 가중치 유무로 구분
- 인접 행렬은 O(V²) 메모리·O(1) 연결 확인, 인접 리스트는 O(V + E) 메모리·빠른 이웃 순회
- 문제를 보면 먼저 격자형인지, 간선 목록형인지 판단한다.
관련 노트: BFS, DFS, 다익스트라, 최소 신장 트리, 서로소 집합, 단절점과 단절선, 오일러 회로, 트리와 이진 탐색 트리, 위상 정렬, 최단 경로 알고리즘 고르기