코딩 테스트에서 그래프 문제는 단골이다. 네트워크 연결 확인, 최단 경로 찾기, 사이클 탐지... 이 모든 문제가 그래프 알고리즘으로 풀린다. 이 글에서는 그래프의 기본 개념부터 주요 알고리즘까지 정리한다.

그래프 추상 데이터 타입

여러 지점과 그 지점들을 잇는 길들처럼, 현실 세계의 많은 문제들은 그래프 라는 개념을 통해 해결할 수 있다.

그래프 G 는 2개의 집합 V와 E로 구성됩니다. V는 공집합이 아닌 정점(Vertice) 들의 유한 집합이며, G는 정점 쌍들의 집합으로 이러한 쌍을 간선 이라 합니다. V(G) 와 E(G)는 각 각 정점과 간선들의 집합을 의미합니다. 그래프는 정점에서 특정 정점으로 가는데에 방향의 개념이 존재하는 경우와 존재하지 않는 경우로 나눌 수 있으며, 이렇게 정점에서 정점으로 이동시 방향이 있는 경우를 방향 그래프(directed graph) 라고 하며, 방향이 없는 경우 무방향 그래프(undirected graph) 라고 합니다.

여기서 정점에 연결된 간선의 수를 차수 라고 하며, Euler는 각 정점의 차수가 짝수 인 경우에만 임의의 정점에서 출발하여 각 간선을 단 한 번씩만 거치고 출발한 정점으로 되돌아오는 길이 있음을 보였으며, 이를 오일러 행로(Eulerian Walk) 라 부릅니다.

그래프 표현법

무방향 그래프의 간선 (u, v) 방향 그래프의 간선 <u, v>

그래프의 기본 연산

깊이 우선 탐색(DFS)

위처럼 인접 리스트 표현법의 경우 간선의 횟수 만큼만 탐색이 진행되므로, O(e) 의 복잡도를 가진다. 하지만 인접 매트릭스 표현으로 표현한 경우 각 정점마다 다른 정점들과 비교해야 하므로 O(n^2) 의 복잡도를 가진다.

너비 우선 탐색(BFS)

시간 복잡도: 인접 리스트 O(V+E), 인접 행렬 O(V²)

개인적인 생각: DFS와 BFS 중 언제 뭘 쓸지 헷갈릴 수 있다. 간단한 기준은:

• 모든 경로 탐색, 사이클 탐지: DFS
• 최단 경로(가중치 없는 그래프): BFS
• 레벨별 탐색: BFS

BFS는 큐를 쓰고, DFS는 스택(또는 재귀)을 쓴다는 것도 기억하자.

신장 트리(spanning tree)

신장 트리란 G의 간선들로만 구성되고 G의 모든 정점을 포함하는 트리를 말합니다. 신장 트리를 만들기 위해서는 DFS 혹은 BFS를 모두 이용할 수 있으며, DFS를 이용하여 만들어진 신장트리를 깊이 우선 신장 트리(depth first spanning tree) 라 하고, BFS를 이용하여 만들어진 신장 트리를 너비 우선 신장 트리(breath first spanning tree) 라 부릅니다.

최소 비용 신장 트리

가중치가 부여된 무방향 그래프의 신장 트리의 비용은 신장 트리를 구성하는 간선들의 비용의 합이 됩니다. 여기서 최소 비용 신장 트리 란 최저의 비용을 갖는 신장트리를 의미합니다.

이 경우 다음의 조건을 만족해야 합니다.

1. 그래프 내에 있는 간선만을 사용해야 한다.
2. 정확히 n-1개의 간선만을 사용해야 한다.
3. 사이클을 생성하는 간선은 사용하면 안된다.

Kruskal 알고리즘

Prim 알고리즘

최단 경로와 이행적 폐쇄

현대의 많은 지도 시스템들은 임의의 두 특정 지점 사이의 경로를 탐색하는 많은 시스템 중의 일부입니다. 경로 탐색 시스템은 일반적으로 주나 전국의 도로 시스템을 표현하기 위하여 그래프를 이용합니다. 이러한 문제에서 도시 A에서 도시 B로 가려는 운전자는 다음과 같은 사항들이 궁금할 것입니다.

1. A로 부터 B로 가는 길이 있는가?
2. A로부터 B로 가는 길이 2갱 이상이라면, 어느 길이 최단으로 가는 길인가?

Dijkstra 알고리즘, 하나의 출발점에서 모든 목표점: 음이 아닌 간선 비용의 경우

다이크스트라 알고리즘

---

마무리

그래프 알고리즘 정리:

알고리즘	용도	시간 복잡도
DFS	모든 정점 방문, 사이클 탐지	O(V+E)
BFS	최단 경로(무가중치), 레벨 탐색	O(V+E)
Kruskal	최소 신장 트리	O(E log E)
Prim	최소 신장 트리	O(E log V)
Dijkstra	단일 출발점 최단 경로	O(E log V)

개인적인 생각: 코딩 테스트에서 그래프 문제가 나오면, 먼저 "이게 어떤 유형인지" 파악하는 게 중요하다.

• "연결되어 있는지 확인" → DFS/BFS
• "최소 비용으로 모든 정점 연결" → 최소 신장 트리 (Kruskal/Prim)
• "A에서 B까지 최단 거리" → Dijkstra (가중치 있을 때), BFS (가중치 없을 때)

이 패턴만 익혀두면 대부분의 그래프 문제는 풀 수 있다.