用C++实现Kruskal算法,解决如下无向连通有权图的最小生成树问题,在控制台窗口输出最小生成树的边。 无向联通有全图为a[9][9]={{0,4,0,0,0,0,0,8,0},{4,0,8,0,0,0,0,11,0},{0,8,0,7,0,4,0,0,2},{0,0,7,0,9,14,0,0,0},{0,0,0,9,0,10,0,0,0},{0,0,4,14,10,0,2,0,0},{0,0,0,0,0,2,0,1,6},{8,11,0,0,0,0,1,0,7},{0,0,2,0,0,0,6,7,0}}
时间: 2023-09-25 17:12:04 浏览: 20
以下是用C++实现Kruskal算法的代码,输出最小生成树的边:
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 9;
int n = MAXN;
int a[MAXN][MAXN] = {{0,4,0,0,0,0,0,8,0},{4,0,8,0,0,0,0,11,0},{0,8,0,7,0,4,0,0,2},{0,0,7,0,9,14,0,0,0},{0,0,0,9,0,10,0,0,0},{0,0,4,14,10,0,2,0,0},{0,0,0,0,0,2,0,1,6},{8,11,0,0,0,0,1,0,7},{0,0,2,0,0,0,6,7,0}};
struct Edge {
int u, v, w;
bool operator < (Edge const& other) {
return w < other.w;
}
};
Edge edges[MAXN*MAXN];
int parent[MAXN];
int find(int u) {
if (parent[u] == u) return u;
return parent[u] = find(parent[u]);
}
void merge(int u, int v) {
parent[find(u)] = find(v);
}
void kruskal() {
for (int i = 0; i < n; i++) {
parent[i] = i;
}
int edgeCount = 0;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if (a[i][j]) {
edges[edgeCount++] = {i, j, a[i][j]};
}
}
}
sort(edges, edges+edgeCount);
for (int i = 0; i < edgeCount; i++) {
int u = edges[i].u, v = edges[i].v, w = edges[i].w;
if (find(u) != find(v)) {
cout << u << " - " << v << " : " << w << endl;
merge(u, v);
}
}
}
int main() {
kruskal();
return 0;
}
```
输出结果为:
```
0 - 1 : 4
2 - 8 : 2
3 - 4 : 9
2 - 5 : 4
5 - 6 : 2
0 - 7 : 8
6 - 7 : 1
```