- 浏览: 600292 次
- 来自: ...
文章分类
最新评论
-
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 1644POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
图的练习题(有解答)
2012-12-27 22:23 26521. 填空题 ⑴ 设无向图G ... -
邻接表实现图的广搜和深搜(java模板)
2012-12-11 17:04 2452//邻接表实现图的广搜和深搜(java模板) impor ... -
邻接矩阵实现图的广搜和深搜(java模板)
2012-12-10 20:37 1909经常要用到,放到这里备用!! //邻接矩阵实现图的广搜和深搜 ... -
如何求无向图的最小环
2012-11-13 19:02 2777POJ1734 题意:给定一个N个点的无向图,求一个最小环(各 ... -
深度优先搜索输出有向图中的所有环(JAVA)
2012-11-06 14:22 9617如图:求出有向图的所有环。 import java.uti ... -
三种算法(Floyd、Dijkstra、SPFA)求单源点最短路径。
2012-11-05 13:15 1845题(HDU2544): 在每年的校赛里,所有进入决赛 ... -
Dijkstra算法解HDU1874
2012-11-05 10:15 1343Dijkstra算法是用来解 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1922很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
图解Bellman-Ford算法
2012-11-03 19:39 5922Bellman-Ford算法: ... -
Bellman-Ford算法教学PPT
2012-11-03 12:06 1450Dijkstra算法是处理单源最短路径的有效算法,但它 ... -
昆虫的同性恋
2012-11-01 19:21 1392题目大意: 输入一个数t,表示测试组数。然后每组第一行两 ... -
拓扑排序入门练习
2012-11-01 16:51 1576拓扑排序简单来说 ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 4043一、什么是并查集 ... -
无前趋的顶点优先的拓扑排序方法(JAVA)
2012-10-28 20:20 1856无前趋的顶点优先的拓扑排序方法 该方法的每一步总是输 ... -
Kruskal算法和prim算法求最小生成树学习小结(JAVA)
2012-10-26 14:02 5037prim算法是用来实现图最小生成树的2种常用方法之一,P ... -
图的邻接表存储及遍历(JAVA)
2012-10-10 10:58 5419为图的每个顶点所发出的边建立一个单链表,用一顶点数组存储 ... -
弗洛伊德(Floyd)算法求任意两点间的最短路径
2012-10-01 07:46 6288Floyd-Warshall算法(Floyd-Warsha ... -
单源最短路径( Dijkstra算法)JAVA实现
2012-09-14 14:30 9107单源最短路径问题,即在图中求出给定顶点到其它任一顶 ... -
深度优先搜索与有向无环图的拓扑排序(java实现)
2012-09-11 13:05 5519当每个任务有前后置关系时,需要找到一种满足前后置关系的路 ...
相关推荐
《克鲁斯卡尔算法:构建最小生成树的精要解析》 在图论的世界里,寻找最优化解决方案是一项常见的挑战。其中,构造最小生成树(Minimum Spanning Tree, MST)是一个核心问题,它旨在找到一个无环连通子图,使得连接...
在MATLAB环境中实现克鲁斯卡尔算法,你可以参考名为"kruskal.m"的文件。这个文件很可能是包含了克鲁斯卡尔算法的具体实现,通过读取图的邻接矩阵或者边列表,进行上述步骤的计算。而"huan.m"文件可能是一个辅助函数...
在这个场景下,我们将深入探讨两种经典算法:克鲁斯卡尔算法(Kruskal's Algorithm)和普利姆算法(Prim's Algorithm)。 首先,克鲁斯卡尔算法是一种贪心策略,其基本思想是从最小的边开始逐步连接顶点,但要确保...
克鲁斯卡尔算法是解决最小生成树问题的一种常用方法,该算法可以用于计算无向图的最小生成树。该算法的实现可以使用C/C++语言编写。 在克鲁斯卡尔算法中,图的存储采用邻接矩阵存储结构,邻接矩阵是一个二维数组,...
在通信网理论作业3-最小生成树这个项目中,你可能会学习如何用MATLAB编写代码,实现Prim和Kruskal算法,并对给定的网络图数据进行最小生成树的构造。这将涉及到数据结构的设计、图的遍历以及最小生成树的验证等编程...
数据结构课程设计报告最小生成树Kruskal算法 数据结构课程设计报告中,我们将使用Kruskal算法来生成最小生成树,该算法是图论中的一种经典算法,能够在给定的图中找到最小生成树。下面,我们将对Kruskal算法的实现...
通过普里姆算法和克鲁斯卡尔算法,我们可以有效地构建最小生成树。普里姆算法适合于稠密图,而克鲁斯卡尔算法则更适合稀疏图。此外,选择邻接矩阵还是邻接表进行存储也会影响算法的效率。 通过上述分析,我们了解了...
克鲁斯卡尔(Kruskal)算法是一种求解最小生成树的经典算法,由约瑟夫·克鲁斯卡尔在1956年提出。以下是克鲁斯卡尔算法的详细解释: 1. **算法步骤**: - **初始化**:创建一个空的集合来存储最终的最小生成树的边...
### 使用Prim和Kruskal算法构建最小生成树 在图论中,最小生成树(Minimum Spanning Tree, MST)是一个非常重要的概念。对于一个连通的无向图来说,如果存在一个子图,它包含原图的所有顶点,并且这些顶点通过边...
克鲁斯卡尔算法(Kruskal's Algorithm)是求解最小生成树的一种经典方法,由约瑟夫·克鲁斯卡尔在1956年提出。本项目以Java编程语言实现了这一算法,并结合图形界面,使得理解和应用更加直观。 首先,我们要理解...
本文档描述的项目是使用C/C++编程语言实现克鲁斯卡尔算法,以构建最小生成树。最小生成树问题通常出现在网络连接优化场景中,例如在n个城市间建立通信网络,目标是以最低成本连接所有城市。克鲁斯卡尔算法就是解决这...
克鲁斯卡尔算法(Kruskal's Algorithm)是一种用于寻找加权无向图的最小生成树的算法。最小生成树是指连接图中所有顶点的树,且边的权重之和最小。在构建通信网络或优化基础设施布局等实际问题中,克鲁斯卡尔算法...
### Python 实现 Kruskal(克鲁斯卡尔)算法构建最小生成树 #### 最小生成树的概念 最小生成树(Minimum Spanning Tree, MST)是针对一个无向加权连通图的一种特殊子图结构。它能够连接图中的所有顶点(节点),并且...
克鲁斯卡尔算法的基本思想是贪心策略,它按照边的权重从小到大进行选择,每次选取一条与当前生成树不形成环的边。具体步骤如下: 1. **初始化**:将图中的所有边按权重排序。 2. **创建空树**:初始时,最小生成树...
总结,克鲁斯卡尔算法是C#实现最小生成树的一种高效方法,结合并查集数据结构可以避免环路的形成。在实际编程中,要关注算法的时间复杂度和空间复杂度,以及如何优化代码以提高性能。同时,理解算法背后的逻辑和图论...
- 通过克鲁斯卡尔算法的实现,理解了如何在实际编程中解决最小生成树问题。 - 学习了并查集等数据结构的应用,提高了算法设计能力。 9. **参考文献** - 可能参考的书籍和论文,如《算法导论》、《数据结构与算法...
克鲁斯卡尔算法(Kruskal's Algorithm)是一种用于构造最小生成树的经典算法,它遵循“贪心”策略,即在每一步中都选择当前未加入树中的权值最小的边,只要这条边不形成环路。 在克鲁斯卡尔算法的实现中,通常需要...