📌 최소 신장 트리 (MST, Minimum Spanning Tree)

🔹 MST란?

• 모든 정점을 연결하면서 간선 가중치 합이 최소가 되는 트리

• 사이클이 없고, N개의 정점이면 N-1개의 간선을 가짐

• 네트워크, 도로망, 전력망 최적화 등에 활용됨

🔹 MST 알고리즘

1️⃣ 크루스칼 (Kruskal) 알고리즘

1. 설명:

• 간선 중심 → 가중치가 작은 간선부터 선택 (정렬 후 유니온-파인드 사용)

• 사이클이 발생하지 않도록 연결하면서 최소 신장 트리를 구축

2. 시간 복잡도: O(E log E)

3. 적용 사례:

• 간선 개수가 적을 때 (E가 V보다 작을 때) 유리

4. 예제 코드 (C++)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge { int u, v, weight; };

vector<int> parent;
int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
void merge(int a, int b) { parent[find(a)] = find(b); }

int main() {
    int N, M;
    cin >> N >> M;
    vector<Edge> edges(M);
    parent.resize(N + 1);
    for (int i = 1; i <= N; i++) parent[i] = i;
    for (auto& e : edges) cin >> e.u >> e.v >> e.weight;

    sort(edges.begin(), edges.end(), [](Edge a, Edge b) { return a.weight < b.weight; });

    int totalCost = 0, count = 0;
    for (auto& e : edges) {
        if (find(e.u) != find(e.v)) {
            merge(e.u, e.v);
            totalCost += e.weight;
            if (++count == N - 1) break;
        }
    }

    cout << totalCost << endl;
}

2️⃣ 프림 (Prim) 알고리즘

1. 설명:

• 정점 중심 → 하나의 정점에서 시작해 최소 가중치 간선을 추가

• 방문한 정점에서 가장 가중치가 작은 간선을 추가하며 트리를 확장

2. 시간 복잡도: O(E log V)