笔记来源：中国大学MOOC王道考研
连通图：图中任意两点都是连通的，那么图被称作连通图
生成树：连通图包含全部顶点的一个极小连通子图
最小生成树：在含有n个顶点的带权无向连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树（不一定唯一）。
性质1：不一定唯一性质2：如果所有边的权重都不相同，则一定唯一性质3：如果连通图只有n-1条边，则最小生成树就是它本身性质4：最小生成树的边数为n-1步骤如下：
初始化，取任意顶点加入结果树：
加入A相邻的且不在结果树中，并且是最小权值的点C
加入与A，C相邻的且不在结果树中，并且是最小权值的点B（BC最小）
重复上述步骤，直到所有顶点都进入结果树：
java代码实现如下：
我们需要用两个数组来实现过程：
min_weight[n]：当前结果树到所有顶点的最短距离adjvex[n]：adjvex[C]=0，代表C是通过A加入结果树的（0是A的下标） /* * 首先我们给出图的存储结构 */ package MST; import java.util.List; public class Graph { /* * 点的存储 */ private List<String> vex; /* * 边的存储 */ private int edges[][]; public Graph(List<String> vex, int[][] edges) { this.vex = vex; this.edges = edges; } public List<String> getVex() { return vex; } public void setVex(List<String> vex) { this.vex = vex; } public int[][] getEdges() { return edges; } public void setEdges(int edges[][]) { this.edges = edges; } public int getVexNum() { return vex.size(); } public int getEdgeNum() { return edges.length; } }然后初始化图：
public class Prime { int m = Integer.MAX_VALUE; int[][] edges = { {0, 3, 1, m, 4}, {3, 0, 2, m, m}, {1, 2, 0, 5, 6}, {m, m, 5, 0, m}, {4, m, 6, m, 0}, }; //打印最小生成树 void MST_Prime(Graph G) { int vexNum = G.getVexNum();//节点个数 int[] min_weight = new int[vexNum];//当前结果树到所有顶点的最短距离 int[] adjvex = new int[vexNum];//adjvex[C]=0，代表C是通过A加入结果树的（0是A的下标） /*初始化两个辅助数组*/ for(int i = 0; i < vexNum; i++) { min_weight[i] = (G.getEdges())[0][i];//第一个顶点到其余顶点的距离 adjvex[i]=0; } int min_edg;//当前挑选的最小权值 int min_vex = 0;//最小权值对应的节点下标 /*循环剩余n-1个点*/ for(int i = 1; i < vexNum; i++) { min_edg = Integer.MAX_VALUE; for(int j = 1; j < vexNum; j++) { if(min_weight[j]!=0 && min_weight[j] < min_edg) { //寻找还没有被挑选进来的，最小权重的点 min_edg = min_weight[j]; min_vex = j; } } min_weight[min_vex] = 0;//纳入结果树 /*修改对应辅助数组的值*/ for(int j = 0; j < vexNum; j++) { if(min_weight[j]!=0 && (G.getEdges())[min_vex][j]<min_weight[j] && (G.getEdges())[min_vex][j]>0) { min_weight[j] = (G.getEdges())[min_vex][j]; adjvex[j]=min_vex; } } int pre = adjvex[min_vex]; int end = min_vex; System.out.println("("+G.getVex().get(pre)+","+G.getVex().get(end)+")"); } } //初始化图 Graph init() { List<String> vex=new ArrayList<String>(); vex.add("A"); vex.add("B"); vex.add("C"); vex.add("D"); vex.add("E"); Graph graph = new Graph(vex, edges); return graph; } public static void main(String[] args) { Prime prime = new Prime(); Graph graph = prime.init(); prime.MST_Prime(graph); } }打印结果如下：
(A,C) (C,B) (A,E) (C,D)
步骤如下：
每个顶点都是独立的树
挑选最短的边AC，加入边集中
依次加入BC，AB，但是AB构成了回路，舍弃
重复直到取了n-1条边
java代码实现如下：
使用 并查集、堆排序、kruskal算法
引用并查集博客：Java实现并查集
//首先我们实现并查集（用来判断是否构成回路--是否属于一个并查集） public class UnionFindSet { //查询树的根 public static int find(int x, int [] par){ if(par[x] == x){ return x; }else{ //压缩路径，第二次查询可以直接返回x的根而不用递归 return par[x] = find(par[x], par); } } //合并 public static void unite(int x, int y, int [] par, int [] rank){ x = find(x, par); y = find(y, par); if(x == y){ return ; } if(rank[x] < rank[y]){ par[x] = y; }else{ par[y] = x; if(rank[x] == rank[y]) rank[x]++; } } //判断x和y是否属于同一个集合 public static boolean same(int x, int y, int [] par){ return find(x, par) == find(y, par); } }然后实现堆排序（稍作修改）：
堆排序参考这篇博客：Java实现堆排序和图解
public class HeapSort { public static void sort(Edge[] arr){ //1.构建大顶堆 for(int i=arr.length/2-1;i>=0;i--){ //从第一个非叶子结点从下至上，从右至左调整结构 adjustHeap(arr,i,arr.length); } //2.调整堆结构+交换堆顶元素与末尾元素 for(int j=arr.length-1;j>0;j--){ swap(arr,0,j);//将堆顶元素与末尾元素进行交换 adjustHeap(arr,0,j);//重新对堆进行调整 } } /** * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上） * @param arr * @param i * @param length */ public static void adjustHeap(Edge[] arr,int i,int length){ Edge temp = arr[i];//先取出当前元素i for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始 if(k+1<length && arr[k].weight<arr[k+1].weight){//如果左子结点小于右子结点，k指向右子结点 k++; } if(arr[k].weight >temp.weight){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换） arr[i] = arr[k]; i = k; }else{ break; } } arr[i] = temp;//将temp值放到最终的位置 } /** * 交换元素 * @param arr * @param a * @param b */ public static void swap(Edge[] arr,int a ,int b){ Edge temp=arr[a]; arr[a] = arr[b]; arr[b] = temp; } }最后我们实现Kruskal算法：
package MST; import java.util.ArrayList; import java.util.List; public class Kruskal { int m = Integer.MAX_VALUE; int[][] arr = { {0, 3, 1, m, 4}, {3, 0, 2, m, m}, {1, 2, 0, 5, 6}, {m, m, 5, 0, m}, {4, m, 6, m, 0}, }; Graph init() { List<String> vex=new ArrayList<String>(); vex.add("A"); vex.add("B"); vex.add("C"); vex.add("D"); vex.add("E"); Graph graph = new Graph(vex, arr); return graph; } //kruskal算法 void MST_Kruskal(Graph G, Edge[] edges, int[] parents, int[] rank) { HeapSort.sort(edges);//堆排序 for(int i = 0; i < G.getEdgeNum(); i++) { if(!UnionFindSet.same(edges[i].a, edges[i].b, parents)) { UnionFindSet.unite(edges[i].a, edges[i].b, parents, rank); System.out.println("("+G.getVex().get(edges[i].a)+","+G.getVex().get(edges[i].b)+")"); } } } public static void main(String[] args) { Kruskal kruskal = new Kruskal(); Graph graph = kruskal.init(); int[] parents = {0,1,2,3,4}; int[] rank = {1,1,1,1,1}; Edge[] edges = new Edge[10]; int index = 0; for(int i = 0; i < 5;i++) { for(int j=0;j<i;j++) { edges[index] = new Edge(); edges[index].weight = kruskal.arr[i][j]; edges[index].a = i; edges[index++].b = j; } } kruskal.MST_Kruskal(graph, edges, parents, rank); } }输出结构为：
(C,A) (C,B) (E,A) (D,C)
