최소 신장 트리 - 크루스칼/프림 알고리즘

트리(Tree)

무향 그래프 G가 순환이 없는 연결그래프이면, G는 트리
노드가 n개이면 간선은 n-1개

신장 트리(Spanning Tree)

무향 연결 그래프 G의 부분그래프이고, G의 모든 정점을 포함하는 트리인 그래프

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

무향 연결 가중 그래프 G에서 간선의 가중치 합이 최소인 신장 트리

크루스칼 알고리즘(Kruskal’s Algorithm)

union-find 이용
이미 연결된 노드 → 연결 x
연결하려는 두 정점이 같은 집합인지 검사(find), 연결(union)
간선의 수 == 노드의 수-1 일때까지 반복

구현

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

struct edge {
    int from, to, cost;
};
bool compare(edge a, edge b) {
    return a.cost < b.cost;
}

int n, m; // #node, #edge
vector<int> parent;
vector<edge> edgeList;

void init() {
    for (int i = 1; i <= n; i++) parent[i] = i;
}
int find(int a) {
    if (parent[a] == a) return a;
    return parent[a] = find(parent[a]);
}
void uni_on(int a, int b) {
    int aRoot = find(a);
    int bRoot = find(b);
    if (aRoot != bRoot) parent[bRoot] = aRoot;
}

int kruskal() {
    init(); 

    int sum = 0, edgeCount = 0;
  
    for (int i = 0; i < edgeList.size(); i++) {
			if (find(edgeList[i].from) != find(edgeList[i].to)) {
			  uni_on(edgeList[i].from, edgeList[i].to);
	
				sum += edgeList[i].cost;
				edgeCount++;
			}
	
			if (edgeCount == n - 1) return sum;
		}
	
		return -1; //만들기 실패(연결 불가한 노드 존재)
}

int main() {
    cin >> n >> m;
    
    parent.resize(n + 1);
    edgeList.resize(m);

    for (int i = 0; i < m; i++) {
        cin >> edgeList[i].from >> edgeList[i].to >> edgeList[i].cost;
    }
    
    sort(edgeList.begin(), edgeList.end(), compare); 

    kruskal();
    
    return 0;
}

프림 알고리즘(Prim’s Algorithm)

우선순위 큐 이용(+ visited 배열)
시작 정점에서 출발하여 가장 작은 가중치를 가진 간선 선택
방문한 노드 확인 후 중복 선택 방지

구현

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

struct edge {
    int to, cost;
};

struct compare {
    bool operator() (edge a, edge b) {
        return a.cost > b.cost;
    }
};

int n, m; // #node, #edge
vector<vector<edge>> adjList;

int prim() {
  	int sum = 0;
		int selectedNodeCount=0;
	
		priority_queue<edge, vector<edge>, compare> pq;
		pq.push({ 1, 0 }); // 시작점이 1, 1으로 가는 cost가 0
	
		vector<bool> selected(n + 1, false);
	
		while (!pq.empty()) {
			edge cur = pq.top();
			pq.pop();
	
			if (selected[cur.to]) continue;
	
			selected[cur.to] = true;
			sum += cur.cost;
			selectedNodeCount++;
	
	    // 모든 정점이 선택되면 종료
			if (selectedNodeCount == n) return sum;
	
			for (edge next : adjList[cur.to]) {
				if (!selected[next.to])
					pq.push(next);
			}
		}
	
		return -1;
}

int main() {
    cin >> n >> m;
    adjList.resize(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v, cost;
        cin >> u >> v >> cost;
        adjList[u].push_back({v, cost});
        adjList[v].push_back({u, cost}); 
    }

    prim();
    
    return 0;
}