一、Kruskal算法核心
- Kruskal算法和Prime算法一样也是计算最小生成树的一种算法。考虑问题的出发点: 为使生成树上边的权值之和达到最小,则应使生成树中每一条边的权值尽可能地小。
- 具体做法: 先构造一个只含 n 个顶点的子图 SG,然后从权值最小的边开始,若它的添加不使SG 中产生回路,则在 SG 上加上这条边,如此重复,直至加上 n-1 条边为止。
- 算法演示
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiIml2ZuMmYhJTMhNmMkJTZ40iMiBTOtM2YzMTLkVzM40iYlhTOxIGN38CX5AjN38CX0ETMw8CX05WZth2YhRHdh9CXkF2bsBXdvwVbvNmLllXZ0lmLywGZvw1LcpDc0RHaiojIsJye.gif)
二、代码实现(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
拓扑图和算法筛选过程:
【数据结构】【图论】【最小生成树】Kruskal算法 四、ACM
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiIml2ZuMmYhJTMhNmMkJTZ40iMiBTOtM2YzMTLkVzM40iYlhTOxIGN38CX5AjN38CX0ETMw8CX05WZth2YhRHdh9CXkF2bsBXdvwVbvNmLllXZ0lmLywGZvw1LcpDc0RHaiojIsJye.gif)
题目链接: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,然而这个数在创建生成树的过程中并没有被使用到。