11.1 최소 비용 신장 트리
Spanning tree(신장 트리)
신장 트리란 주어진 연결 그래프(Connected Graph) G=(V,E)에서,
- 모든 정점 V를 포함
- 사이클이 없는 트리 구조
- V - 1개의 간선을 갖는 부분 그래프
즉,
"모든 정점을 포함하되, 사이클 없이, 최소한의 간선으로 연결된 서브그래프"이다.
신장 트리는 DFS, BFS 도중에 사용된 간선만 모으면 만들 수 있다. 예를 들어 DFS 알고리즘을 변경하여 신장 트리를 구해보면 다음과 같다. 큐를 사용하여 간선들을 저장할 수 있다.
depth_first_search(v):
v를 방문되었다고 표시;
for all u ∈ (v에 인접한 정점) do
if (u가 아직 방문되지 않았으면)
then (v,u)를 신장 트리 간선이라고 표시;
depth_first_search(u)신장 트리는 그래프의 최소 연결 부분 그래프가 된다. 여기서 최소의 의미는 간선의 수가 가장 적다는 의미이다. n개의 정점을 가지는 그래프는 최소한 (n-1)개의 간선을 가져야 하며, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것은 바로 신장 트리가 된다.
신장 트리는 어디에 사용될까? 신장 트리는 통신 네트워크 구축에 많이 사용된다. 예를 들어 n개의 위치를 연결하는 통신 네트워크를 최소의 링크를 이용하여 구축하고자 할 경우, 최소 링크 수는 (n-1)이 되고 따라서 신장 트리들이 가능한 대안이 된다.
그러나 각 링크의 구축 비용은 똑같지가 않다. 따라서 단순히 가장 적은 링크만을 사용한다고 해서 최소 비용이 얻어지는 것은 아니다. 따라서 각 링크, 즉 간선에 비용을 붙여서 링크의 구축 비용까지를 고려하여 최소 비용의 신장 트리를 선택할 필요가 있다.
Minimum spanning tree(최소 비용 신장 트리)
최소 비용 신장 트리는 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리를 말한다.
11.2 Kruskal의 MST 알고리즘
크루스칼 알고리즘(Kruskal’s Algorithm)은 가중치 그래프의 최소 신장 트리를 구하는 그리디 알고리즘이다.
가중치가 낮은 간선부터 선택하고, 사이클이 생기지 않도록 정점을 연결해 나간다.
크루스칼 알고리즘은 최적의 해답을 주는 것으로 증명되어 있다.(Cut property)
알고리즘 핵심 개념
- 모든 간선을 가중치 기준 오름차순 정렬
- 가중치가 가장 작은 간선부터 하나씩 선택
- 선택한 간선이 사이클을 만들지 않으면 MST에 포함
- MST에 포함된 간선이 (V − 1)개가 될 때까지 반복
사이클 여부는 Disjoint Set(= Union-Find) 자료구조로 확인
Union-Find 자료구조
크루스칼에서 사이클 생성을 방지하기 위해 사용한다.
find(x): x의 루트(parent)를 찾음 (경로 압축 사용)union(x, y): x와 y가 속한 두 집합을 합침 (랭크 기준 합치기)
int[] parent = new int[n];
void makeSet() {
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]); // 경로 압축
return parent[x];
}
void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) parent[rootY] = rootX;
}구현
import java.util.*;
class Edge implements Comparable<Edge> {
int from, to, weight;
Edge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
public int compareTo(Edge o) {
return this.weight - o.weight;
}
}
public class KruskalMST {
static int[] parent;
static int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]); // 경로 압축
return parent[x];
}
static void union(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA != rootB)
parent[rootB] = rootA;
}
public static int kruskal(int v, List<Edge> edges) {
Collections.sort(edges); // 1. 간선 정렬
parent = new int[v];
for (int i = 0; i < v; i++) parent[i] = i; // makeSet
int mstWeight = 0;
int edgeCount = 0;
for (Edge e : edges) {
if (find(e.from) != find(e.to)) { // 2. 사이클 발생 안 하면
union(e.from, e.to); // 3. Union
mstWeight += e.weight;
edgeCount++;
if (edgeCount == v - 1) break; // MST 완성
}
}
return mstWeight;
}
}시간 복잡도
| 단계 | 시간 복잡도 |
|---|---|
간선 정렬 (Collections.sort) | O(E log E) |
| union-find 연산 (경로 압축 포함) | O(α(V)) per operation (거의 O(1)) |
| 전체 합계 | O(E log E) (보통 E > V이므로 정렬이 가장 큼) |
※ α(V)는 아커만 함수의 역함수 → 거의 상수
장단점
| 항목 | 내용 |
|---|---|
| ✅ 장점 | 정점보다 간선 수가 적은 희소 그래프에 매우 효율적 |
| ❌ 단점 | 간선 정렬로 인해 간선이 많은 조밀 그래프에는 비효율적 |
11.3 Prim의 MST 알고리즘
Prim 알고리즘은 가중치 그래프의 최소 신장 트리(MST) 를 구하는 그리디 알고리즘이다.
알고리즘 핵심 개념
- 하나의 시작 정점에서 시작하여
- 인접한 가장 짧은 간선을 하나씩 추가하면서
- 트리를 확장해 나간다.
연결된 정점 집합과 연결되지 않은 정점 집합 사이의 간선 중 가장 가중치가 작은 간선을 선택함
알고리즘 동작 절차
- 아무 시작 정점을 선택하고 MST에 포함
- 현재 MST에 인접한 가장 짧은 간선을 선택
- 선택된 간선이 연결하는 정점이 MST에 없으면 MST에 추가
- 모든 정점이 MST에 포함될 때까지 반복
구현 (PriorityQueue 사용)
import java.util.*;
class Edge {
int to, weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
public class PrimMST {
public static int prim(int v, List<List<Edge>> graph) {
boolean[] visited = new boolean[v];
PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
pq.add(new Edge(0, 0)); // 시작 정점은 0, 가중치 0
int mstWeight = 0;
while (!pq.isEmpty()) {
Edge edge = pq.poll();
int u = edge.to;
if (visited[u]) continue;
visited[u] = true;
mstWeight += edge.weight;
for (Edge next : graph.get(u)) {
if (!visited[next.to]) {
pq.add(next);
}
}
}
return mstWeight;
}
}시간 복잡도
| 자료구조 | 복잡도 |
|---|---|
| 인접 행렬 + 배열 | O(V²) |
| 인접 리스트 + PriorityQueue | O(E log V) (추천) |
Prim vs Kruskal 비교
| 항목 | Prim | Kruskal |
|---|---|---|
| 탐색 기준 | 정점 중심 (Vertex-based) | 간선 중심 (Edge-based) |
| 자료구조 | PriorityQueue + visited[] | Edge List + Union-Find |
| 정렬 여부 | 간선 정렬 ❌ | 간선 정렬 필요 (O(E log E)) |
| 사용 추천 | 조밀 그래프 (Dense Graph) | 희소 그래프 (Sparse Graph) |
| 구현 복잡도 | 상대적으로 복잡함 | 상대적으로 간단함 |
| 사이클 방지 방식 | visited[] 체크 | Union-Find로 집합 분리 확인 |
11.4 최단 경로
최단 경로(shortest path) 문제는 네트워크에서 정점 i와 정점 j를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제이다. 간선의 가중치는 비용, 거리, 시간 등을 나타낸다.
11.5 Dijkstra의 최단 경로 알고리즘
Dijkstra의 최단 경로 알고리즘은 가중치가 있는 그래프에서 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다.
모든 간선의 가중치가 0 이상(음수 없음)이라는 조건이 있어야 정확하게 동작한다.
알고리즘 핵심 개념
- 입력: 가중치가 있는 방향 또는 무방향 그래프, 시작 정점
- 출력: 시작 정점에서 모든 정점까지의 최단 거리
- 전제 조건: 간선 가중치가 음수가 없어야 함
- 전략:
- 시작 정점에서부터 거리가 가장 짧은 정점을 하나씩 선택
- 해당 정점을 통해 갈 수 있는 이웃 정점들의 최단 거리 갱신
- 반복
알고리즘 동작 과정
- 시작 정점의 거리는 0, 나머지는 ∞로 초기화
- 우선순위 큐(PriorityQueue)를 사용해 아직 방문하지 않은 정점 중 거리 최소인 정점 선택
- 선택한 정점을 기준으로, 인접한 정점들의 거리를 갱신
- 모든 정점이 처리될 때까지 2~3 반복
구현
import java.util.*;
class Dijkstra {
static class Edge {
int to, weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
static class Node implements Comparable<Node> {
int vertex, distance;
Node(int vertex, int distance) {
this.vertex = vertex;
this.distance = distance;
}
public int compareTo(Node o) {
return Integer.compare(this.distance, o.distance);
}
}
public static int[] dijkstra(int V, List<List<Edge>> graph, int start) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(start, 0));
while (!pq.isEmpty()) {
Node current = pq.poll();
if (dist[current.vertex] < current.distance) continue;
for (Edge edge : graph.get(current.vertex)) {
int newDist = dist[current.vertex] + edge.weight;
if (newDist < dist[edge.to]) {
dist[edge.to] = newDist;
pq.offer(new Node(edge.to, newDist));
}
}
}
return dist;
}
}시간복잡도
| 항목 | 복잡도 |
|---|---|
| 자료구조 | 우선순위 큐(PriorityQueue, Min-Heap) |
| 간선 수 , 정점 수 | |
| 최악 시간복잡도 | |
| → PriorityQueue에서 최소 거리 정점 추출 + 이웃 간선 순회 | |
| Dense 그래프 (E ≈ V²) | 느림 |
| Sparse 그래프 (E ≈ V) | 빠름 (효율적) |
11.6 Floyd의 최단 경로 알고리즘
- 모든 정점 쌍 (i, j) 사이의 최단 거리를 구하는 알고리즘
- 동적 프로그래밍(DP) 기반
- 음수 간선 허용 가능, 단 음수 사이클은 허용 불가
- 모든 정점 쌍에 대해 최단 거리를 구해야 할 때 효율적
동작 원리
- 3중 루프를 돌며 "i에서 j로 가는 최단 경로"를 k를 거쳐 갱신
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
구현
import java.util.Arrays;
public class FloydWarshall {
static final int INF = 1_000_000_000; // 충분히 큰 값
public static int[][] floydWarshall(int[][] graph) {
int V = graph.length;
int[][] dist = new int[V][V];
// 초기화
for (int i = 0; i < V; i++) {
dist[i] = Arrays.copyOf(graph[i], V);
}
// 핵심 알고리즘
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][k] < INF && dist[k][j] < INF) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
return dist;
}
public static void main(String[] args) {
int INF = 1_000_000_000;
int[][] graph = {
{ 0, 3, INF, 7 },
{ 8, 0, 2, INF },
{ 5, INF, 0, 1 },
{ 2, INF, INF, 0 }
};
int[][] result = floydWarshall(graph);
// 출력
for (int i = 0; i < result.length; i++) {
for (int j = 0; j < result.length; j++) {
System.out.print((result[i][j] == INF ? "INF" : result[i][j]) + "\t");
}
System.out.println();
}
}
}시간 복잡도
| 항목 | 복잡도 |
|---|---|
| 정점 수 | |
| 시간 복잡도 | |
| 공간 복잡도 |
📌 간선 수 E에 상관없이 전체 정점 쌍 확인 → Sparse 그래프에 비효율적
하지만 모든 정점 쌍의 최단 경로가 필요할 땐 가장 직관적
특이사항 / 장점
- 간선 가중치가 음수여도 사용 가능 (단, 음수 사이클은 안 됨)
- 다중 쿼리(모든 정점 쌍의 최단 거리) 처리 시 매우 유용
- 간단한 경로 복원도 가능 (추가 배열
next[i][j]사용)
Dijkstra vs Floyd-Warshall 비교
| 항목 | Dijkstra | Floyd-Warshall |
|---|---|---|
| 목적 | 한 정점 → 모든 정점 | 모든 정점 쌍 |
| 음수 가중치 | ❌ 불가 | ✅ 가능 (음수 사이클은 ❌) |
| 시간 복잡도 | (우선순위 큐) | |
| 공간 복잡도 | or | |
| 그래프 밀도 | Sparse 그래프에 적합 | Dense 그래프에 적합 |
| 사용 예시 | 경로 탐색, 네비게이션 등 | 거리 행렬 계산, 플로우 최적화 등 |
11.7 위상 정렬(Topological sorting)
- 방향 비순환 그래프(DAG)에서 노드를 순서대로 정렬하는 알고리즘
- 간선 (u → v)은 u가 먼저, v가 나중에 나와야 함
- 일반적인 용도: 작업 순서 정하기, 의존성 해결
예시 상황
- 과목 선수과목 → 어떤 과목을 먼저 들어야 하는지?
- 빌드 시스템 → 어떤 파일을 먼저 컴파일해야 하는지?
- 패키지 설치 순서 → 어떤 라이브러리를 먼저 설치해야 하는지?
전제 조건
- 그래프는 반드시 DAG (Directed Acyclic Graph) 여야 함
- 사이클이 존재하면 위상 정렬은 불가능
알고리즘 방식
방식 1: DFS 기반 위상 정렬
- 후위 순회로 정점을 탐색한 후, 역순으로 나열
- 재귀 호출이 끝난 순서대로 스택에 삽입
방식 2: 진입 차수(Kahn's Algorithm) 기반
- 진입 차수(in-degree)가 0인 정점을 먼저 큐에 삽입
- 해당 정점을 제거하면서 이웃 정점의 진입 차수를 감소시킴
구현(진입 차수 기반, Kahn's Algorithm)
import java.util.*;
public class TopologicalSort {
public static List<Integer> topologicalSort(int V, List<List<Integer>> adj) {
int[] inDegree = new int[V];
for (int u = 0; u < V; u++) {
for (int v : adj.get(u)) {
inDegree[v]++;
}
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < V; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
List<Integer> order = new ArrayList<>();
while (!queue.isEmpty()) {
int u = queue.poll();
order.add(u);
for (int v : adj.get(u)) {
inDegree[v]--;
if (inDegree[v] == 0) {
queue.offer(v);
}
}
}
if (order.size() != V) {
throw new RuntimeException("사이클이 존재하여 위상 정렬 불가능");
}
return order;
}
public static void main(String[] args) {
int V = 6;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
// 예제: 5 → 2, 5 → 0, 4 → 0, 4 → 1, 2 → 3, 3 → 1
adj.get(5).add(2);
adj.get(5).add(0);
adj.get(4).add(0);
adj.get(4).add(1);
adj.get(2).add(3);
adj.get(3).add(1);
List<Integer> result = topologicalSort(V, adj);
System.out.println("Topological Order: " + result);
}
}시간복잡도
| 항목 | 복잡도 |
|---|---|
| 정점 수 , 간선 수 | |
| 시간 복잡도 | |
| 공간 복잡도 | (인접 리스트 기준) |
- 각 정점과 간선을 한 번씩 방문
- 인접 행렬을 사용할 경우 공간복잡도는 𝑂(V^2)
Reference
절단 성질을 이용한 MST 알고리즘 증명 (Proving MST Algorithms by Cut Property)
Backend engineer