如何使用C 中的最小生成樹演算法
最小生成樹（Minimum Spanning Tree，MST）是圖論中一個重要的概念，它表示連接一個無向連通圖的所有頂點的邊的子集，且這些邊的權值總和最小。有多種演算法可以用來求解最小生成樹，如Prim演算法和Kruskal演算法。本文將介紹如何使用C 實作Prim演算法和Kruskal演算法，並給出具體的程式碼範例。
Prim演算法是一種貪心演算法，它從圖的一個頂點開始，逐步選擇與當前最小生成樹連接的權值最小的邊，並將該邊加入到最小生成樹中。以下是Prim演算法的C 程式碼範例：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 1e9;
int prim(vector<vector<pair<int, int>>>& graph) {
int n = graph.size(); // 图的顶点数
vector<bool> visited(n, false); // 标记顶点是否已访问
vector<int> dist(n, INF); // 记录顶点到最小生成树的最短距离
int minCost = 0; // 最小生成树的总权值
// 从第一个顶点开始构建最小生成树
dist[0] = 0;
// 使用优先队列保存当前距离最小的顶点和权值
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push(make_pair(0, 0));
while (!pq.empty()) {
int u = pq.top().second; // 当前距离最小的顶点
pq.pop();
// 如果顶点已访问过，跳过
if (visited[u]) {
continue;
}
visited[u] = true; // 标记顶点为已访问
minCost += dist[u]; // 加入顶点到最小生成树的权值
// 对于顶点u的所有邻接顶点v
for (auto& edge : graph[u]) {
int v = edge.first;
int weight = edge.second;
// 如果顶点v未访问过，并且到顶点v的距离更小
if (!visited[v] && weight < dist[v]) {
dist[v] = weight;
pq.push(make_pair(dist[v], v));
}
}
}
return minCost;
}
int main() {
int n, m; // 顶点数和边数
cin >> n >> m;
vector<vector<pair<int, int>>> graph(n);
// 读取边的信息
for (int i = 0; i < m; ++i) {
int u, v, w; // 边的两个顶点及其权值
cin >> u >> v >> w;
--u; --v; // 顶点从0开始编号
graph[u].push_back(make_pair(v, w));
graph[v].push_back(make_pair(u, w));
}
int minCost = prim(graph);
cout << "最小生成树的权值之和为：" << minCost << endl;
return 0;
}Kruskal演算法是一種基於邊的貪心演算法，它從圖的所有邊中選擇權值最小的邊，並判斷該邊是否會形成環路。如果不會形成環路，則將該邊加入最小生成樹。以下是Kruskal演算法的C 程式碼範例：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
int u, v, weight; // 边的两个顶点及其权值
Edge(int u, int v, int weight) : u(u), v(v), weight(weight) {}
};
const int MAXN = 100; // 最大顶点数
int parent[MAXN]; // 并查集数组
bool compare(Edge a, Edge b) {
return a.weight < b.weight;
}
int findParent(int x) {
if (parent[x] == x) {
return x;
}
return parent[x] = findParent(parent[x]);
}
void unionSet(int x, int y) {
int xParent = findParent(x);
int yParent = findParent(y);
if (xParent != yParent) {
parent[yParent] = xParent;
}
}
int kruskal(vector<Edge>& edges, int n) {
sort(edges.begin(), edges.end(), compare);
int minCost = 0; // 最小生成树的总权值
for (int i = 0; i < n; ++i) {
parent[i] = i; // 初始化并查集数组
}
for (auto& edge : edges) {
int u = edge.u;
int v = edge.v;
int weight = edge.weight;
// 如果顶点u和顶点v不属于同一个连通分量，则将该边加入到最小生成树中
if (findParent(u) != findParent(v)) {
unionSet(u, v);
minCost += weight;
}
}
return minCost;
}
int main() {
int n, m; // 顶点数和边数
cin >> n >> m;
vector<Edge> edges;
// 读取边的信息
for (int i = 0; i < m; ++i) {
int u, v, w; // 边的两个顶点及其权值
cin >> u >> v >> w;
edges.push_back(Edge(u, v, w));
}
int minCost = kruskal(edges, n);
cout << "最小生成树的权值之和为：" << minCost << endl;
return 0;
}透過上述程式碼範例，我們可以在C 中使用Prim演算法和Kruskal演算法求解最小生成樹的問題。在實際應用中，可以根據具體情況選擇合適的演算法來解決問題。這些演算法的時間複雜度分別為O(ElogV)和O(ElogE)，其中V為頂點數，E為邊數。因此，它們在處理大規模圖的情況下也能夠得到較好的效果。
以上是如何使用C++中的最小生成樹演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！
