一、Kruskal算法核心
- Kruskal算法和Prime算法一样也是计算最小生成树的一种算法。考虑问题的出发点: 为使生成树上边的权值之和达到最小,则应使生成树中每一条边的权值尽可能地小。
- 具体做法: 先构造一个只含 n 个顶点的子图 SG,然后从权值最小的边开始,若它的添加不使SG 中产生回路,则在 SG 上加上这条边,如此重复,直至加上 n-1 条边为止。
- 算法演示
二、代码实现(Java版)
import java.util.Comparator; import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.Scanner; import java.util.Set; import java.util.TreeSet; class Edge { int node1; int node2; int edgeValue; } class MySort implements Comparator<Edge> { public int compare(Edge o1, Edge o2) { return o1.edgeValue > o2.edgeValue ? 1 : -1; } } public class Kruskal { static final int maxNodeValue = (1 << 31) - 1; public static void main(String args[]) { Scanner scanner = new Scanner(System.in); Set<Edge> edges = new TreeSet<Edge>(new MySort()); Map<Integer, Integer> preNode = new HashMap<Integer, Integer>(); while (scanner.hasNext()) { int edgeCounts = scanner.nextInt(); for (int i = 0; i < edgeCounts; i++) { int node1 = scanner.nextInt(); int node2 = scanner.nextInt(); int edgeValue = scanner.nextInt(); Edge oldEdge = findOldEdge(node1, node2, edges); if (oldEdge != null) { if (oldEdge.edgeValue > edgeValue) { Edge edge = new Edge(); edge.edgeValue = edgeValue; edge.node1 = node1; edge.node2 = node2; edges.add(edge); } } else { Edge edge = new Edge(); edge.edgeValue = edgeValue; edge.node1 = node1; edge.node2 = node2; edges.add(edge); } } int cost = kruskal(edges, preNode); System.out.println(cost); edges.clear(); preNode.clear(); } } private static Edge findOldEdge(int node1, int node2, Set<Edge> edges) { Iterator<Edge> iterator = edges.iterator(); while (iterator.hasNext()) { Edge edge = iterator.next(); if ((edge.node1 == node1 && edge.node2 == node2) || (edge.node1 == node2 && edge.node2 == node1)) { return edge; } } return null; } public static int findRootNode(Integer node, Map<Integer, Integer> preNode) { while (preNode.get(node) != null) { node = preNode.get(node); } return node; } public static int kruskal(Set<Edge> edges, Map<Integer, Integer> preNode) { Iterator<Edge> it = edges.iterator(); int cost = 0; while (it.hasNext()) { Edge edge = it.next(); int node1 = edge.node1; int node2 = edge.node2; int edgeValue = edge.edgeValue; int node1_parent=findRootNode(node1, preNode) ; int node2_parent=findRootNode(node2, preNode); if (node1_parent!=node2_parent) { preNode.put(node1_parent, node2_parent); cost += edgeValue; } } return cost; } }
三、测试用例
输入
11
1 2 19
1 5 14
1 7 18
2 3 5
2 4 7
2 5 12
3 4 3
4 5 8
4 6 21
5 7 16
6 7 27
输出
67
11
1 2 19
1 5 14
1 7 18
2 3 5
2 4 7
2 5 12
3 4 3
4 5 8
4 6 21
5 7 16
6 7 27
输出
67
拓扑图和算法筛选过程:
四、ACM
题目链接:http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2144
AC代码:
import java.util.Comparator; import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.Scanner; import java.util.Set; import java.util.TreeSet; class Edge { int node1; int node2; int edgeValue; } class MySort implements Comparator<Edge> { public int compare(Edge o1, Edge o2) { return o1.edgeValue > o2.edgeValue ? 1 : -1; } } public class Main{ static final int maxNodeValue = (1 << 31) - 1; public static void main(String args[]) { Scanner scanner = new Scanner(System.in); Set<Edge> edges = new TreeSet<Edge>(new MySort()); Map<Integer, Integer> preNode = new HashMap<Integer, Integer>(); while (scanner.hasNext()) { int nodeCounts = scanner.nextInt(); int edgeCounts = scanner.nextInt(); for (int i = 0; i < edgeCounts; i++) { int node1 = scanner.nextInt(); int node2 = scanner.nextInt(); int edgeValue = scanner.nextInt(); Edge oldEdge = findOldEdge(node1, node2, edges); if (oldEdge != null) { if (oldEdge.edgeValue > edgeValue) { Edge edge = new Edge(); edge.edgeValue = edgeValue; edge.node1 = node1; edge.node2 = node2; edges.add(edge); } } else { Edge edge = new Edge(); edge.edgeValue = edgeValue; edge.node1 = node1; edge.node2 = node2; edges.add(edge); } } int cost = kruskal(edges, preNode); System.out.println(cost); edges.clear(); preNode.clear(); } } private static Edge findOldEdge(int node1, int node2, Set<Edge> edges) { Iterator<Edge> iterator = edges.iterator(); while (iterator.hasNext()) { Edge edge = iterator.next(); if ((edge.node1 == node1 && edge.node2 == node2) || (edge.node1 == node2 && edge.node2 == node1)) { return edge; } } return null; } public static int findRootNode(Integer node, Map<Integer, Integer> preNode) { while (preNode.get(node) != null) { node = preNode.get(node); } return node; } public static int kruskal(Set<Edge> edges, Map<Integer, Integer> preNode) { Iterator<Edge> it = edges.iterator(); int cost = 0; while (it.hasNext()) { Edge edge = it.next(); int node1 = edge.node1; int node2 = edge.node2; int edgeValue = edge.edgeValue; int node1_parent=findRootNode(node1, preNode) ; int node2_parent=findRootNode(node2, preNode); if (node1_parent!=node2_parent) { preNode.put(node1_parent, node2_parent); cost += edgeValue; } } return cost; } }
AC代码和上面的代码只有一点不同,那就是输入了节点的个数nodeCount,然而这个数在创建生成树的过程中并没有被使用到。
相关推荐
图论算法:最小生成树——Prim算法和Kruskal算法C 实现
用Kruskal避圈算法求最小生成树的源代码
图论中最小生成树算法,使用ruskal进行处理
洛谷原模板题p3366 题目网址: https://www.luogu.com.cn/problem/P3366
最小生成树:minimum spanning tree 在连通网的所有生成树中,所有边的代价和最小的生成树,称为最小生成树。 Kruskal不是最小生成树的最有效算法,但却是学习图论必不可少的一步。 本代码旨在帮助初学图论的编程...
利用Kruskal避圈算法求解图论中的最小生成树问题
《算法导论》之图论章节中最小生成树的Kruskal算法。
matlab算法,可以解决最小生成树算法以及类似问题关于最小生成树,学过图论的都懂,这里就不做介绍。 下面是一个例题,附有Kruskal算法和Prim算法。
Kruskal 算法是图论中的一种算法,它为连通的无向加权图找到最小生成树 压缩文件包含 kruskal.m iscycle.m fysalida.m connected.m 如果我们想找到最小生成树。 我们称之为函数 kruskal。 % 输入:PV = nx3 martix...
Kruskal求最小生成树。用此法可求出最小生成树。图论中学到的知识。
在Matlab中利用避圈法(Kruskal算法、克鲁斯卡尔算法)求解图的最小生成树的程序
用R语言实现Kruskal算法,搜索图的最小生成树,并计算出权重,文件里有图例,有语言代码,复制即可运行,每个步骤有详细注释,并配有结果图
Kruskal 算法是一种最小生成树算法,该算法找到连接森林中任意两棵树的权重尽可能小的边。 它是图论中的一种贪心算法,因为它在每一步都为连通的加权图找到最小生成树。 注意:使用 mst.txt 文件作为树的输入
求最小生成树的避圈法之一——克鲁斯卡尔算法
采用Dijkstra和Floyd算法寻找最小路径;采用Kruskal和Prism算法构造最小生成树;
Kruskals算法状态:已完成Kruskal的算法是最小生成树算法,该算法找到连接森林中任意两棵树的权重最小的边缘。 它是图论中的贪婪算法,因为它找到了最小生成树。 为了使算法起作用,您将需要一个文本文件,该文件...
第二步是利用最小生成树原理,结合Kruskal算法得出最小生成树;第三步是参照依照约束条件对最小代价数进行优化,得到最短距离1927.1071米。 对于问题二,问题一的基础上增加了一个矩形海洋馆,可继续借助第一个问题...
2.2 Kruskal算法和Prim算法 3 单源最短路径 3.1 Bellman-Ford算法 3.2 有向无环图(DAG图)中单源最短路径问题 3.3 Dijkstra算法 3.4 差分约束和最短路径 3.5 最短路径的性质证明(三上无路收钱) 4 所有结点对的...
这就叫最小生成树算法,最典型的两种算法就是Kruskal算法和本文要讲的Prim算法。 2.Prim算法的步骤是什么? 这就要涉及一些图论的知识了。 a.假定图的顶点集合为V,边集合为E. b.初始化点集合U={u}.//u为V中的任意...