數據結構——最小生成樹

在圖論中，最小生成樹（Minimum Spanning Tree, MST）是在一個帶權重的無向連通圖中找到一棵包含所有頂點且邊權之和最小的子樹。兩個常用算法是普裡姆算法和克魯斯卡爾算法。

1. 普裡姆算法

普裡姆算法采用貪心策略，逐步從已加入MST的節點出發，選擇與未加入集合的節點相連的最小權值邊來擴充MST。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void prim(int n) {
	vector<bool> visited(n, false);
	vector<int> key(n, INT_MAX); // 邊權初始為無窮大
	priority_queue<pair<int, int>> pq; // 優先隊列按權值排序
	// 初始化，任選一節點
	int start = 0;
	key[start] = 0;
	pq.push({ 0, start });
	while (!pq.empty()) {
		int u = pq.top().second;
		pq.pop();
		if (!visited[u]) {
			visited[u] = true;
			for (auto& edge : adj[u]) { // 遍歷u的鄰接邊
				int v = edge.first;
				int weight = edge.second;
				if (!visited[v] && weight < key[v]) {
					key[v] = weight;
					pq.push({ key[v], v });
				}
			}
		}
	}
}
// 在主函數中調用 prim 函數並初始化圖結構

2. 克魯斯卡爾算法

克魯斯卡爾算法同樣是貪心方法，按照邊權從小到大排序後，依次添加不構成環的邊。

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
struct Edge {
	int src, dest, weight;
	bool operator<(const Edge& other) const {
		return weight < other.weight;
	}
};
void kruskal(int n) {
	sort(edges.begin(), edges.end()); // 按權重排序
	vector<Edge> mst;
	// 使用並查集判斷加入邊是否會形成環，此處省略實現細節
	for (Edge e : edges) {
		if (!formsCycle(e.src, e.dest)) { // 自定義的檢測環函數
			mst.push_back(e);
			unionSets(e.src, e.dest); // 合並集合
		}
	}
}
// 在主函數中調用 kruskal 函數，並完成並查集和相關數據結構的初始化

以上代碼僅展示了兩種算法的核心邏輯，實際編程時需補充完整並查集操作以及輸出部分。註意，在處理大規模稀疏圖時，應考慮使用鄰接表而非鄰接矩陣來優化空間效率。