- 浏览: 584619 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
算法描述:Kruskal(克鲁斯卡尔)算法需要对图的边进行访问,所以克鲁斯卡尔算法的时间复杂度只和边又关系。
算法过程:
1.将图各边按照权值进行排序
2.将图遍历一次,找出权值最小的边,(条件:此次找出的边不能和已加入最小生成树集合的边构成环),若符合条件,则加入最小生成树的集合中。不符合条件则继续遍历图,寻找下一个最小权值的边。
3.递归重复步骤1,直到找出n-1条边为止(设图有n个结点,则最小生成树的边数应为n-1条),算法结束。得到的就是此图的最小生成树。
运行:
C:\test>java KruskalTest
请输入测试次数:
2
5 8
0 1 2
1 4 9
1 2 8
4 3 7
3 0 10
0 2 12
2 3 6
2 4 3
0-->1
2-->4
2-->3
1-->2
19.0
7 9
0 1 28
1 2 16
2 3 12
0 5 10
4 3 22
4 6 24
4 5 25
1 6 14
3 6 18
0-->5
2-->3
1-->6
1-->2
4-->3
4-->5
99.0
下载源码:
算法过程:
1.将图各边按照权值进行排序
2.将图遍历一次,找出权值最小的边,(条件:此次找出的边不能和已加入最小生成树集合的边构成环),若符合条件,则加入最小生成树的集合中。不符合条件则继续遍历图,寻找下一个最小权值的边。
3.递归重复步骤1,直到找出n-1条边为止(设图有n个结点,则最小生成树的边数应为n-1条),算法结束。得到的就是此图的最小生成树。
import java.util.Scanner; import java.util.Arrays; public class KruskalTest{ private int father[]; private int son[]; private Edge e[]; private int n;//结点个数 private int l;//边的数目 public KruskalTest(int n,int l,Edge[] e){ this.n=n; this.l=l; this.e=e; father=new int[n]; son=new int[n]; for(int i = 0; i < n; ++i){ father[i] = i;//将每个顶点初始化为一个集合,父节点指向自己。 son[i]=1;//初始化每个父节点的儿子数为1 } } public static void main(String args[]){ Scanner scan = new Scanner(System.in); System.out.println("请输入测试次数:"); int ncase = scan.nextInt(); //测试次数 while((ncase--)!=0){ int n = scan.nextInt(); //图的顶点数 int l = scan.nextInt(); //图的边数 Edge[] e=new Edge[l]; for(int i = 0; i < l ; ++i){//输入边的数据 int a=scan.nextInt(); int b=scan.nextInt(); double weight=scan.nextDouble(); e[i]=new Edge(a,b,weight); } KruskalTest spt = new KruskalTest(n,l,e); System.out.println(spt.kruskal()); } } public int unionsearch(int x){ //查找根结点+路径压缩 return (x == father[x]) ? x : unionsearch(father[x]); } public boolean join(int x, int y){ //合并 int root1, root2; root1 = unionsearch(x); root2 = unionsearch(y); if(root1 == root2){ //为环 return false; } else if(son[root1] >= son[root2]){ father[root2] = root1; son[root1] += son[root2]; } else { father[root1] = root2; son[root2] += son[root1]; } return true; } public double kruskal(){ double sum=0; int ltotal=0; boolean flag=false; Arrays.sort(e); //按权值由小到大排序 for(int i = 0; i < l; ++i) { if(join(e[i].a, e[i].b)==true) { ltotal++; //边数加1 sum += e[i].weight; //记录权值之和 System.out.println(e[i].a+"-->"+e[i].b); } if(ltotal == n - 1) //最小生成树条件:边数=顶点数-1 { flag = true; break; } } if(flag) return sum; else{ System.out.println("此图没有最小生成树"); return -1; } } } class Edge implements Comparable { int a; //边的一个顶点,从数字0开始 int b; //边的另一个顶点 double weight; //权重 Edge(int a,int b,double weight){ this.a=a; this.b=b; this.weight=weight; } @Override public int compareTo(Object o){ Edge m = (Edge)o; int result=(int)(this.weight - m.weight); if(result>0) return 1; else if(result==0) return 0; else return -1; } }
运行:
C:\test>java KruskalTest
请输入测试次数:
2
5 8
0 1 2
1 4 9
1 2 8
4 3 7
3 0 10
0 2 12
2 3 6
2 4 3
0-->1
2-->4
2-->3
1-->2
19.0
7 9
0 1 28
1 2 16
2 3 12
0 5 10
4 3 22
4 6 24
4 5 25
1 6 14
3 6 18
0-->5
2-->3
1-->6
1-->2
4-->3
4-->5
99.0
下载源码:
- KruskalTest.zip (1.3 KB)
- 下载次数: 4
发表评论
-
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1528POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
图的练习题(有解答)
2012-12-27 22:23 26141. 填空题 ⑴ 设无向图G ... -
邻接表实现图的广搜和深搜(java模板)
2012-12-11 17:04 2410//邻接表实现图的广搜和深搜(java模板) impor ... -
邻接矩阵实现图的广搜和深搜(java模板)
2012-12-10 20:37 1845经常要用到,放到这里备用!! //邻接矩阵实现图的广搜和深搜 ... -
如何求无向图的最小环
2012-11-13 19:02 2742POJ1734 题意:给定一个N个点的无向图,求一个最小环(各 ... -
深度优先搜索输出有向图中的所有环(JAVA)
2012-11-06 14:22 9556如图:求出有向图的所有环。 import java.uti ... -
三种算法(Floyd、Dijkstra、SPFA)求单源点最短路径。
2012-11-05 13:15 1779题(HDU2544): 在每年的校赛里,所有进入决赛 ... -
Dijkstra算法解HDU1874
2012-11-05 10:15 1304Dijkstra算法是用来解 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1868很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
图解Bellman-Ford算法
2012-11-03 19:39 5822Bellman-Ford算法: ... -
Bellman-Ford算法教学PPT
2012-11-03 12:06 1402Dijkstra算法是处理单源最短路径的有效算法,但它 ... -
昆虫的同性恋
2012-11-01 19:21 1356题目大意: 输入一个数t,表示测试组数。然后每组第一行两 ... -
拓扑排序入门练习
2012-11-01 16:51 1536拓扑排序简单来说 ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 3989一、什么是并查集 ... -
无前趋的顶点优先的拓扑排序方法(JAVA)
2012-10-28 20:20 1790无前趋的顶点优先的拓扑排序方法 该方法的每一步总是输 ... -
Kruskal算法和prim算法求最小生成树学习小结(JAVA)
2012-10-26 14:02 4967prim算法是用来实现图最小生成树的2种常用方法之一,P ... -
图的邻接表存储及遍历(JAVA)
2012-10-10 10:58 5356为图的每个顶点所发出的边建立一个单链表,用一顶点数组存储 ... -
弗洛伊德(Floyd)算法求任意两点间的最短路径
2012-10-01 07:46 6222Floyd-Warshall算法(Floyd-Warsha ... -
单源最短路径( Dijkstra算法)JAVA实现
2012-09-14 14:30 9038单源最短路径问题,即在图中求出给定顶点到其它任一顶 ... -
深度优先搜索与有向无环图的拓扑排序(java实现)
2012-09-11 13:05 5471当每个任务有前后置关系时,需要找到一种满足前后置关系的路 ...
相关推荐
Kruskal克鲁斯卡尔算法构造最小生成树的动画实现!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!1111
最小生成树的经典算法。我在代码中加入了详细的文字解释。并以算法导论第二版书中例子为例,得到了相同结果。
第3关求图(邻接矩阵存储)最小生成树的克鲁斯卡尔(Kruskal)算法 第4关求图(邻接表存储)最小生成树的克鲁斯卡尔(Kruskal)算法 稳过 生成树是将图中所有顶点以最少的边连通的子图。权值和最小的生成树就是最小...
Prim与Kruskal算法的最小生成树matlab实现
建立一个图,其存储方式采用邻接矩阵形式,利用普里姆算法和克鲁斯卡尔算法求网的最小生成树,按顺序输出生成树中各条边以及它们的权值。
数据结构,最小生成树克鲁斯卡尔算法的实现.pdf
kruskal算法,最小生成树算法,内有示例,也可改成函数(在示例状态下被注释,要改成函数,取消那个注释,改下函数名或者文件名就行)
C#,最小生成树(MST)克鲁斯卡尔(Kruskal)算法的源代码。克鲁斯卡尔(Kruskal)算法是一种用来寻找最小生成树的算法,由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都...
克鲁斯卡尔算法构造最小生成树常见的算法,该程序是采用Kruskal算法求解最小生成树问题(邻接矩阵和邻接表)。
C#最小生成树算法之Kurskal算法,基于Vs2010,控制台窗体,可直接实现
1、最小生成树的概念; 2、Prim算法及其实现; 3、Kruskal算法及其实现; 4、图的表示; 5、边的表示; 6、优先队列priority_queue的自定义排序 7、大根堆、小根堆的区别 8、结构体的构建 面向对象: 有一定C++基础...
克鲁斯卡尔算法是算法中常见的算法,该程序是采用Kruskal算法求解最小生成树问题。
一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有足以构成一棵树的n-1条边。 当用联通网来表示n个城市以及n个城市间可能...(1)编写Kruskal算法代码,实现图的最小生成树求解,且输出最小生成树。
假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网,则按照克鲁斯卡尔算法构造最小生成树的过程为:先构造一个只含 n 个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点,则它是一个含有 n 棵树的...
克鲁斯卡下面答卷分别就课程的销售预测、市场满意度指标、市场占有率指标、计划准确度指标,展开讨论。 尔最小生成树的C语言算法
多种方法求解最小生成树问题的PDF文件 赋权有向图的最小生成树算法; 基于Kruskal算法的最小生成树的构建; 普里姆算法和克鲁斯卡尔算法构造最小生成树; 用遗传算法求最小生成树等。
—————————最小... (1)利用克鲁斯卡尔算法求网的最小生成树。 (2)实现教科书6.5节中定义的抽象树类型 MFSet。以此表示构造生成树过程中的连通分量。 (3)以文本形式输出生成树中各条边以及他们的权值。
克鲁斯卡尔算法的基本思想是:设一个有n个顶点的连通网络G={V,E},先构造一个包括全部n个顶点和0条边的森林F={T0,T1,…,Tn-1},以后每一步向F中加入一条边(v, u),它应是所依附的两个顶点v和u分别在森林F的两棵...
2.领域:智能优化算法、神经网络预测、信号处理、元胞自动机、图像处理、路径规划、无人机等多种领域的Matlab仿真,更多内容可点击博主头像 3.内容:标题所示,对于介绍可点击主页搜索博客 4.适合人群:本科,硕士...