最小生成树之克鲁斯卡尔算法

算法思路

  1. 准备:边类,图类;
  2. 根据图的邻接矩阵获得边集合,并将边按照边的权值进行排序(升序);
  3. 依次取边集合中的边,如果取出来的这条边不和已经选择的边构成回路就添加这条边,否则取边集合中的下一条边。

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)

上一篇:常用十大算法(七)— 克鲁斯卡尔算法


下一篇:Visual Studio Solution Configuration