최소 신장 트리 (MST) - 크루스칼 알고리즘, 프림 알고리즘

1. 신장 트리 (Spanning Tree)

그래프 내 모든 정점을 포함하는 트리다. 그래프의 최소 연결 부분이다.

• 모든 정점이 연결되어 있음
• 사이클이 존재하지 않음
• 간선의 개수 = 정점의 개수 - 1

DFS, BFS를 이용하여 그래프에서 Spanning Tree를 찾을 수 있다. 탐색 도중 사용한 간선만 모으면 된다.

하나의 그래프는 여러 개의 Spanning Tree를 가질 수 있다.

---

2. 최소 신장 트리, (Minimum Spanning Tree)

Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리

• 모든 정점이 연결되어 있음
• 사이클이 존재하지 않음
• 간선의 개수 = 정점의 개수 - 1
• 간선들의 가중치 합이 최소

그리디 알고리즘을 사용하는 대표적인 트리 형태의 자료구조

---

3. MST 구현 방법

3.1 크루스칼 알고리즘

1. 동작 원리

• 간선들을 가중치의 오름차순으로 정렬
• 가장 작은 가중치부터 시작하여 사이클을 형성하지 않는 간선을 선택
• Union-Find 자료구조를 활용하여 사이클 여부 판단

2. 구현 시 포인트

• Union-Find 자료구조 구현
• 간선 정렬
• 사이클 검사

3. 구현

class Edge implements Comparable<Edge> {
    int src, dest, weight;
    
    Edge(int src, int dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }
    
    @Override
    public int compareTo(Edge other) {
        return this.weight - other.weight;
    }
}

class KruskalMST {
    private int[] parent;
    private int[] rank;
    
    private int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    private void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
    
    public List<Edge> kruskal(List<Edge> edges, int V) {
        List<Edge> result = new ArrayList<>();
        parent = new int[V];
        rank = new int[V];
        
        // 초기화
        for (int i = 0; i < V; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
        
        // 간선을 가중치 기준으로 정렬
        Collections.sort(edges);
        
        int edgeCount = 0;
        int index = 0;
        
        while (edgeCount < V - 1 && index < edges.size()) {
            Edge edge = edges.get(index++);
            
            int x = find(edge.src);
            int y = find(edge.dest);
            
            if (x != y) {
                result.add(edge);
                union(x, y);
                edgeCount++;
            }
        }
        
        return result;
    }
}

---

3.2 프림 알고리즘

1. 동작 원리

• 임의의 정점에서 시작
• 현재 트리와 연결된 간선 중 가장 가중치가 작은 간선을 선택 (사이클 형성X)
• 새로운 정점을 트리에 추가

2. 구현 시 포인트

• 우선순위 큐 활용
• 방문 체크 배열
• 최소 가중치 갱신

---

3.3 알고리즘 비교

	크루스칼 (Kruskal)	프림 (Prim)
시간 복잡도	O(E log E) (E는 간선의 개수)	O(E log V) (우선순위 큐 사용 시)
탐색 방법	최소 가중치를 갖는 간선부터 하나씩 추가	임의 정점에서 최소 인접 가중치를 갖는 정점을 추가
상황	간선이 적은 그래프에 적합	간선이 많은 그래프에 적합