求最小生成树算法代码及运行图片

① 用破圈法求最小生成树

感觉上你那里的“算法基本思想”实现难度很大，因为图的连通性不好维护
找圈的话，随便找个节点为根DFS整个图，然后在这样的DFS生成树中，每条非树边都对应了一个圈，每次找一条非树边，删去所在圈中最长边生成一个新树，直到不存在非树边为止，剩下的就是最小生成树了
具体实现的时候，先求出一个DFS生成树，然后递归处理每棵子树

假设要处理的子树根节点为u，对该子树破圈法的粗略伪代码如下：

void 破圈法(u)
{
for ( v是u的每个子节点 ) 破圈法(v);
for ( e是连接u与其后继的每条非树边 )
{
v=e的另一个端点;
e'=u到v之间的最长树边;
if (w[e]>=w[e']) 删除边e;//w[e]表示e的权
else
{
//用w表示原先e'的在树中较深的端点,p[v]表示v的亲节点
删除边e';
if (v!=w)
{
将v列入u的子节点列表;
将p[v]、p[p[v]]、...、w这条路径反向，并将p[v]列入v的子节点列表;
}
}
}
}

上述过程不加优化的时间复杂度为O(VE)，效率非常差
貌似其中找最长边和将v的若干祖先节点路径反向的两步优化空间比较大，或许可将整个时间复杂度下降到O(ElgV)，研究中

② c加加提问，克鲁斯卡尔算法是什么

克鲁斯卡尔算法，从边的角度求网的最小生成树，时间复杂度为O(eloge)。和普里姆算法恰恰相反，更适合于求边稀疏的网的最小生成树。

对于任意一个连通网的最小生成树来说，在要求总的权值最小的情况下，最直接的想法就是将连通网中的所有边按照权值大小进行升序排序，从小到大依次选择。

由于最小生成树本身是一棵生成树，所以需要时刻满足以下两点：

• 生成树中任意顶点之间有且仅有一条通路，也就是说，生成树中不能存在回路；

• 对于具有 n 个顶点的连通网，其生成树中只能有 n-1 条边，这 n-1 条边连通着 n 个顶点。

连接 n 个顶点在不产生回路的情况下，只需要 n-1 条边。

• 所以克鲁斯卡尔算法的具体思路是：将所有边按照权值的大小进行升序排序，然后从小到大一一判断，条件为：如果这个边不会与之前选择的所有边组成回路，就可以作为最小生成树的一部分；反之，舍去。直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。筛选出来的边和所有的顶点构成此连通网的最小生成树。



判断是否会产生回路的方法为：在初始状态下给每个顶点赋予不同的标记，对于遍历过程的每条边，其都有两个顶点，判断这两个顶点的标记是否一致，如果一致，说明它们本身就处在一棵树中，如果继续连接就会产生回路；如果不一致，说明它们之间还没有任何关系，可以连接。

• 假设遍历到一条由顶点 A 和 B 构成的边，而顶点 A 和顶点 B 标记不同，此时不仅需要将顶点 A 的标记更新为顶点 B 的标记，还需要更改所有和顶点 A 标记相同的顶点的标记，全部改为顶点 B 的标记。


（6）



• 当选取的边的数量相比与顶点的数量小 1 时，说明最小生成树已经生成。所以最终采用克鲁斯卡尔算法得到的最小生成树为（6）所示。



• 实现代码：#include "stdio.h"#include "stdlib.h"#define MAX_VERtEX_NUM 20#define VertexType inttypedef struct edge{VertexType initial;VertexType end;VertexType weight;}edge[MAX_VERtEX_NUM];//定义辅助数组typedef struct {VertexType value;//顶点数据int sign;//每个顶点所属的集合}assist[MAX_VERtEX_NUM];assist assists;//qsort排序函数中使用，使edges结构体中的边按照权值大小升序排序int cmp(const void *a,const void*b){return ((struct edge*)a)->weight-((struct edge*)b)->weight;}//初始化连通网void CreateUDN(edge *edges,int *vexnum,int *arcnum){printf("输入连通网的边数： ");scanf("%d %d",&(*vexnum),&(*arcnum));printf("输入连通网的顶点： ");for (int i=0; i<(*vexnum); i++) {scanf("%d",&(assists[i].value));assists[i].sign=i;}printf("输入各边的起始点和终点及权重： ");for (int i=0 ; i<(*arcnum); i++) {scanf("%d,%d,%d",&(*edges)[i].initial,&(*edges)[i].end,&(*edges)[i].weight);}}//在assists数组中找到顶点point对应的位置下标int Locatevex(int vexnum,int point){for (int i=0; i<vexnum; i++) {if (assists[i].value==point) {return i;}}return -1;}int main(){int arcnum,vexnum;edge edges;CreateUDN(&edges,&vexnum,&arcnum);//对连通网中的所有边进行升序排序，结果仍保存在edges数组中qsort(edges, arcnum, sizeof(edges[0]), cmp);//创建一个空的结构体数组，用于存放最小生成树edge minTree;//设置一个用于记录最小生成树中边的数量的常量int num=0;//遍历所有的边for (int i=0; i<arcnum; i++) {//找到边的起始顶点和结束顶点在数组assists中的位置int initial=Locatevex(vexnum, edges[i].initial);int end=Locatevex(vexnum, edges[i].end);//如果顶点位置存在且顶点的标记不同，说明不在一个集合中，不会产生回路if (initial!=-1&& end!=-1&&assists[initial].sign!=assists[end].sign) {//记录该边，作为最小生成树的组成部分minTree[num]=edges[i];//计数+1num++;//将新加入生成树的顶点标记全不更改为一样的for (int k=0; k<vexnum; k++) {if (assists[k].sign==assists[end].sign) {assists[k].sign=assists[initial].sign;}}//如果选择的边的数量和顶点数相差1，证明最小生成树已经形成，退出循环if (num==vexnum-1) {break;}}}//输出语句for (int i=0; i<vexnum-1; i++) {printf("%d,%d ",minTree[i].initial,minTree[i].end);}return 0;}


• 测试数据：



输入连通网的边数：
6 10
输入连通网的顶点：
1
2
3
4
5
6
输入各边的起始点和终点及权重：
1,2,6
1,3,1
1,4,5
2,3,5
2,5,3
3,4,5
3,5,6
3,6,4
4,6,2
5,6,6
1,3
4,6
2,5
3,6
2,3

③ 最小生成树算法描述

最小生成树的求解步骤如下：

• 定义一个初始为空的树T，表示顶点集和边集。


• 重复以下操作，直到T成为图G的生成树：在T中寻找一条安全边（u，v），即加入这条边后T仍保持为MST的子集。


• 将找到的安全边(u，v)添加到T中，扩大T的范围。

这可以用Pascal、Prim算法或Kruskal算法等具体实现，它们的区别在于寻找安全边的方式不同：

• Prim算法：从一个起点v0开始，逐步加入与生成树距离最近的未加入顶点，更新边集。


• Kruskal算法：按权值递增顺序挑选边，每次选择不形成回路的边加入到最小生成树中。

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图联通的最少的边。

④ 求最小生成树的kruska算法，效率尽量高，尽量多点注释！c++代码

/*
基本算法思想：
为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出 n-1 条互不构成回路的权值最小边为止。
具体作法如下：首先构造一个只含 n 个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。
由于生成树上不允许有回路，因此并非每一条居当前权值最小的边都可选。

用并查积 和 克鲁是卡尔算法实现查找最短边
利用快排按边递增排列，每次从中选出最短边,同时将最短边的两个顶点并入到集合中
心得：利用并查积 和 kruskal算法结合找最短路径可以使查找的效率更高
加入集合中的边都是构成最小生成树的边，所以每家一次sum 都要加上这两个顶点之间的距离
*/
/*下面的代码输入n个节点，然后输入n*（n-1）/2条边及权值，输出是连通这些边的最小权值*/
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

struct ed
{
int u; //起始点
int v; //终结点
int w; //权重
};
bool cmp(ed a,ed b)
{
return a.w<b.w; //从小到大排序
}
struct ed edge[100000];
int p[105];

int find(int x) //查找x的父亲
{
while(p[x]!=x)
x=p[x];
return x;
}
int kruskal(int n)
{
int i,count=1,sum=0;
for(i=0;i<=n;i++)
p[i]=i; //并查集初始化，每个节点到父亲是自己
int x,y;
sort(edge,edge+n*(n-1)/2,cmp); //快速排序
for(i=0;count<n;i++)
{
x=find(edge[i].u); //点edge[i].u的父亲是x
y=find(edge[i].v); //点edge[i].v的父亲是y
if(x!=y) //判断是否会路
{
count++; //加上一条边
p[x]=y; //把x和y加入统一个集合
sum+=edge[i].w;
}
}
return sum;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF&&n) //输入n个节点
{
int i;
for(i=0;i<n*(n-1)/2;i++) //输入 n*（n-1）/2条边
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w); //表示点edge[i].u和点edge[i].v之间的权重为 edge[i].w
printf("%d\n",kruskal(n));
}
return 0;
}

楼主，这可是本人一个字一个字敲出来点，要给分啊