算法思路
- 准备:边类,图类;
- 根据图的邻接矩阵获得边集合,并将边按照边的权值进行排序(升序);
- 依次取边集合中的边,如果取出来的这条边不和已经选择的边构成回路就添加这条边,否则取边集合中的下一条边。
Q:怎么判断新取的边和已经选取的边会不会构成回路?
A:引入一个数组,记录每个顶点的终点,如果新取的这条边的两端的终点相同,说明构成回路;否则不构成。
注:终点是指在最小生成树中与它连通的最大顶点。
代码实现
package com.ex.kruskal; import java.util.ArrayList; import java.util.Collections; import java.util.List; public class Kruskal{
static final int INF=10000; //边 static class Edge implements Comparable<Edge>{ int p1; int p2; int weight; public Edge(int p1, int p2, int weight) { this.p1 = p1; this.p2 = p2; this.weight = weight; } @Override public int compareTo(Edge o) { return this.weight-o.weight; } } //图 static class Graph{ char[] nodes; int[][] matrix; List<Edge> edges; public Graph(char[] nodes, int[][] matrix) { this.nodes = nodes; this.matrix = matrix; generateEdges(); } //生成边,并排序 public void generateEdges(){ edges=new ArrayList<>(); for (int i = 0; i < nodes.length; i++) { for (int j = i+1; j < nodes.length; j++) { if (matrix[i][j]!=INF) { edges.add(new Edge(i,j,matrix[i][j])); } } } Collections.sort(edges); } } //生成最小生成树 public static void kruskal(Graph graph){ //准备 char[] nodes = graph.nodes; List<Edge> edges = graph.edges; int[][] matrix = graph.matrix; int[] ends=new int[nodes.length]; //每次选择一个边,如果不构成回路就加入集合,否则下一条边 for (int i = 0; i < edges.size(); i++) { Edge edge = edges.get(i); int end1 = getEnd(ends, edge.p1); int end2 = getEnd(ends, edge.p2); if (end1!=end2) { System.out.println(nodes[edge.p1]+"—>"+nodes[edge.p2]+":"+matrix[edge.p1][edge.p2]); ends[end1]=end2; } } } //获得某个顶点的终点 private static int getEnd(int[] ends,int index){ while (ends[index]!=0){ index=ends[index]; } return index; } public static void main(String[] args) { char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; //克鲁斯卡尔算法的邻接矩阵 int matrix[][] = { { 0, 12, INF, INF, INF, 16, 14}, { 12, 0, 10, INF, INF, 7, INF}, { INF, 10, 0, 3, 5, 6, INF}, { INF, INF, 3, 0, 4, INF, INF}, { INF, INF, 5, 4, 0, 2, 8}, { 16, 7, 6, INF, 2, 0, 9}, { 14, INF, INF, INF, 8, 9, 0}}; //求最小生成树 Graph graph = new Graph(vertexs, matrix); kruskal(graph); } }
普里姆算法 VS 克鲁斯卡尔算法
n:结点数 E:边数
算法名 | 普里姆算法 | 克鲁斯卡尔算法 |
---|---|---|
时间复杂度 | O(n2) | O(ElogE) |
适用范围 |
稠密图 (n、E相当) |
稀疏图 (E<<n) |