写出kruskal算法对应的程序,kruskal算法c++代码

　　00-1010简介1。图2施工后。代码3。测试

　　00-1010还有一种构造最小生成树的算法，即Kruskal算法：设图G=(V，e)是一个无向连通加权图，V={1，2，n }；设最小生成树T=(V，TE)，这棵树的初始状态只有n个节点和无界不连通图t=(v，{})。Kruskal算法将这n个节点视为n个孤立的连通分支。首先将所有边按权重从小到大排序，然后T中要选择的边数小于n-1，于是做了这个贪婪的选择：边集合E中权重最小的边(I，J)，如果将边(I，J)加入集合t E不产生循环，则将边(I，J)加入边集合TE，即边(I，J)否则继续选择下一个最短的边。从集合E中删除边(I，j ),继续上面的贪婪选择，直到T中的所有节点都在同一连通分支上。此时，所选的n-1条边正好构成了图G的最小生成树T.

　　克鲁斯卡尔算法用了一个很巧妙的方法，那就是集合回避；如果所选边的起点和终点都在T集合中，则可以断定会形成一个回路，变化的两个节点不能属于同一个集合。

　　算法步骤

　　1初始化。所有边按权重从小到大排序，每个节点集编号初始化为自己的编号。

　　2选择排序顺序中选项值最小的边(u，v)。

　　3如果节点U和V属于两个不同的连通分支，则将边(U，V)添加到边集TE中，并将两个连通分支合并。

　　4如果选择的边数小于n-1，转到步骤2，否则算法结束。

目录

介绍

包graph.kruskal导入Java . util . ArrayList；导入Java . util . collections；导入Java . util . list；导入Java . util . scanner；公共类Kruskal { static final int N=100static int fa[]=new int[N]；静态int n；静态int m；静态边e[]=新边[N * N]；static ListEdge edge list=new ArrayList()；static { for(int I=0；即长度；I){ e[I]=new Edge()；} }//将集合数初始化为自己的静态void init(int n){ for(int I=1；I=n；I)fa[I]=I；}//Merge静态int merge (int a，int b){ int p=fa[a]；int q=fa[b]；if (p==q)返回0；for(int I=1；I=n；I) {//检查所有节点，如果(fa[i]==q) fa[i]=p，则将集合数Q改为p；//a的集合号赋给B的集合号}返回1；}//求最小生成树静态int kruskal(int n){ int ans=0；collections . sort(edge list)；for(int I=0；我是m；i ) if (Merge(edgeList.get(i))。u，edgeList.get(i)。v)==1) { ans=edgeList.get(i)。w；n-；If (n==1)//n-1合并算法结束返回ans}返回0；} public static void main(String[]args){ Scanner Scanner=new Scanner(system . in)；n=scanner . nextint()；m=scanner . nextint()；初始化(n)；for(int I=1；I=m；i ) { e[i]。u=scanner . nextint()；e[i]。v=scanner . nextint()；e[i]。w=scanner . nextint()；edge list . add(e[I])；} System.out.println(最小开销为： Kruskal(n))；}}类Edge实现可比的{ int u；int w；int v；@ Override public int compare to(Object o){ if(this . w((Edge)o)。w){ return 1；} else if (this.w==((Edge) o)。w){ return 0；} else { return-1；} }}

　　00-1010绿色为输入，白色为输出。

　　本文关于Kruskal算法的Java实现的样例代码到此结束。关于Java Kruskal算法的更多信息，请搜索热门IT之前的文章或者继续浏览下面的相关文章。我希望你以后能更多地支持流行音乐！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。