在kruskal中输出结果
时间: 2024-02-21 18:57:49 浏览: 35
在上面的代码中,我们已经将最小生成树的边存储在了 `EdgeArray mst` 中,可以直接遍历这个数组输出最小生成树的边,即:
```c
for (i = 0; i < mst.n; i++) {
printf("%d %d %d\n", mst.edges[i].u, mst.edges[i].v, mst.edges[i].w);
}
```
输出的格式为:每行输出一条边,格式为起点编号、终点编号、边权重。
相关问题
Kruskal算法的c语言实现,输出结果应该是最小生成树各边权值之和
A:下面是Kruskal算法的C语言实现,同时输出最小生成树的各边权值之和:
```c
#include<stdio.h>
#include<stdlib.h>
#define MAXN 100005
#define MAXM 1000005
typedef struct Edge{
int u,v,w;
}Edge;
Edge edge[MAXM];
int father[MAXN];
int n,m;
int cmp(const void* a,const void* b){
return ((const Edge*)a)->w - ((const Edge*)b)->w;
}
int find(int x){
if(father[x]==x)
return x;
return father[x]=find(father[x]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
qsort(edge+1,m,sizeof(Edge),cmp); //将边按权值从小到大排序
for(int i=1;i<=n;i++)
father[i]=i; //初始化并查集
int ans=0,cnt=0;
for(int i=1;i<=m;i++){
int u=edge[i].u,v=edge[i].v,w=edge[i].w;
int fau=find(u),fav=find(v);
if(fau==fav) //如果两个点已经在同一个集合中,说明加入该边会形成环,跳过该边
continue;
father[fau]=fav; //将两个点合并到同一个集合中
ans+=w; //累加边权值
cnt++; //记录加入的边数
if(cnt==n-1) //如果加入的边数等于点数减1,说明已经构成了一棵最小生成树
break;
}
printf("%d\n",ans); //输出最小生成树的所有边权值之和
return 0;
}
```
kruskal算法 java
Kruskal算法是一种用于求解最小生成树的贪心算法。它的基本思想是将所有边按照权值从小到大排序,然后依次加入到生成树中,如果加入该边不会形成环,则将该边加入生成树中。
以下是Kruskal算法的Java实现:
```java
import java.util.*;
class Edge implements Comparable<Edge> {
int u, v, w;
public Edge(int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
}
public int compareTo(Edge e) {
return this.w - e.w;
}
}
class Kruskal {
int[] parent;
int[] rank;
public Kruskal(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 1;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public void union(int x, int y) {
int px = find(x);
int py = find(y);
if (px == py) {
return;
}
if (rank[px] > rank[py]) {
parent[py] = px;
} else if (rank[px] < rank[py]) {
parent[px] = py;
} else {
parent[py] = px;
rank[px]++;
}
}
public int kruskal(Edge[] edges) {
Arrays.sort(edges);
int n = parent.length;
int res = 0;
for (Edge e : edges) {
if (find(e.u) != find(e.v)) {
union(e.u, e.v);
res += e.w;
}
}
return res;
}
}
public class Main {
public static void main(String[] args) {
int n = 5;
Edge[] edges = new Edge[7];
edges[0] = new Edge(0, 1, 2);
edges[1] = new Edge(0, 2, 3);
edges[2] = new Edge(1, 2, 4);
edges[3] = new Edge(1, 3, 1);
edges[4] = new Edge(2, 3, 5);
edges[5] = new Edge(2, 4, 4);
edges[6] = new Edge(3, 4, 6);
Kruskal kruskal = new Kruskal(n);
int res = kruskal.kruskal(edges);
System.out.println(res); // 输出最小生成树的权值和
}
}
```