文章目录
4.4 最小支撑树(Minimum-cost Spanning Tree)
概念Prim算法——从点出发
算法步骤示例代码实现 Kruskal算法——从边出发
算法步骤示例代码实现 4.4 最小支撑树(Minimum-cost Spanning Tree) 概念
定义
给定一个连通无向图G，且它的每条边均有相应的长度或权值，则MST是一个包括G中的所有顶点及其边子集的图，边的子集满足下列条件:
这个子集中所有边的权之和为所有子集中最小的
子集中的边能够保证图是连通的
环性质
环性质
假设T是一个有权无向图G=(V,E)的MST，如果选择一条属于E，但不属于T的边e加入到MST,从而使T形成一个环时，那么这个环中的任意一条边f都洞足如下关系
weight(f) <= weight(e)
分割性质
设集合U和W是图G=(V,E)的顶点集合的两个子集,这两个顶点子集将图分成了两部分，其中e是所有能够连接两个部分中权最小的边，那么e将是MST的一条边
Prim算法——从点出发 算法步骤
1️⃣ 选择图中的任意一个顶点N开始，初始化MST为N
2️⃣ 计算MST中每个顶点到不在MST中的每个顶点之间的距离
3️⃣ 选择这些距离中最小的那条边，并将这条边中的不在MST中的顶点加入到MST中
4️⃣ 重复步骤2和3，直到没有可以加入到MST中的顶点为止
示例 代码实现
相邻矩阵实现带权无向图
public class GraphMatrix { //用相邻矩阵实现无向图 private ArrayList V;//顶点 private int E;//边数 private int[][] matrix;//相邻矩阵 private int[] mark;//判定一个结点是否被访问过 public static final int VISITED = -2;//已经访问 public static final int UNVISITED = -3;//未访问 public static final int UNConNECTED = 1000;//未访问 public GraphMatrix(int n) { matrix = new int[n][n]; mark = new int[n]; for (int i = 0; i < n; i++) { mark[i] = UNVISITED; for (int j = 0; j < n; j++) { matrix[i][j] = UNCONNECTED; } } V = new ArrayList(n); } public void insertVertex(String vertex) { V.add(vertex); } public void insertEdge(int v1, int v2, int weight) { matrix[v1][v2] = weight; matrix[v2][v1] = weight; E++;//边数+1 } public int getWeight(int v1, int v2) { return matrix[v1][v2]; } public int getEdgeNum() { return E; } public int getVertexNum() { return V.size(); } public String getVertexValue(int index) { return V.get(index); } public int getFirst(int v) { for (int i = 0; i < V.size(); i++) { if (matrix[v][i] > 0) { return i; } } return -1; } public int getNext(int v1, int v2) { for (int i = v2 + 1; i < V.size(); i++) { if (matrix[v1][i] > 0) { return i; } } return -1; } public boolean isEdge(int v1, int v2) { return isLegalIndex(v1) && isLegalIndex(v2) && matrix[v1][v2] > 0; } public boolean isLegalIndex(int v) { return v >= 0 && v < V.size(); } public void DFS() { for (int i = 0; i < getVertexNum(); i++) { setMark(i, UNVISITED); }//初始化所有顶点 for (int i = 0; i < getVertexNum(); i++) { if (getMark(i) == UNVISITED) { DFSHelp(i); } } } public void DFSHelp(int v) { System.out.print(V.get(v) + " "); setMark(v, VISITED); for (int edge = getFirst(v); isEdge(v, edge); edge = getNext(v, edge)) { if (getMark(edge) == UNVISITED) { DFSHelp(edge); } } } public void BFS() { for (int i = 0; i < getVertexNum(); i++) { setMark(i, UNVISITED); }//初始化所有顶点 for (int i = 0; i < getVertexNum(); i++) { if (getMark(i) == UNVISITED) { BFSHelp(i); } } } public void BFSHelp(int v) { LQueue queue = new LQueue<>(); queue.enqueue(v); setMark(v, VISITED); while (!queue.isEmpty()) { int temp = queue.dequeue(); System.out.print(V.get(temp) + " "); for (int index = getFirst(temp); isEdge(temp, index); index = getNext(temp, index)) { if (getMark(index) == UNVISITED) { queue.enqueue(index); setMark(index, VISITED); } } } } public void setMark(int v, int val) { mark[v] = val; } public int getMark(int v) { return mark[v]; } //打印邻接矩阵 public void print() { for (int[] edge : matrix) { System.out.println(Arrays.toString(edge)); } } public static void main(String[] args) { //定义图的所有顶点 String[] vertexs = {"A", "B", "C", "D", "E", "F"}; //创建图 GraphMatrix graph = new GraphMatrix(vertexs.length); //添加顶点到图中 for (String vertex : vertexs) { graph.insertVertex(vertex); } //添加边到图中 graph.insertEdge(0, 2, 1); graph.insertEdge(0, 4, 1); graph.insertEdge(1, 2, 1); graph.insertEdge(1, 5, 1); graph.insertEdge(2, 3, 1); graph.insertEdge(2, 5, 1); graph.insertEdge(3, 5, 1); graph.insertEdge(4, 5, 1); graph.print(); graph.DFS(); System.out.println(); graph.BFS(); }}
public class Prim { private GraphMatrix originalGraph;//用相邻矩阵实现的原图 private ArrayList N;//不在MST集合中的元素下标 private ArrayList S;//在MST集合中的元素下标 private int vertexNum;//顶点数 public void createOriginalGraph(GraphMatrix originalGraph) { this.originalGraph = originalGraph; this.vertexNum = originalGraph.getVertexNum(); this.N = new ArrayList<>(vertexNum); for (int i = 0; i < vertexNum; i++) { N.add(i); } this.S = new ArrayList<>(0); } public void showOriginalGraph() { originalGraph.print(); } public void prim(int start) { int v1 = start; int v2 = originalGraph.getFirst(v1); originalGraph.setMark(v1, GraphMatrix.VISITED); S.add(v1);//加入MST N.remove(v1);//同时从N中移除 for (int i = 0; i < vertexNum - 1; i++) { int miniWeight = GraphMatrix.UNCONNECTED; for (int j = 0; j < S.size(); j++) {//从MST中的顶点 for (int k = 0; k < N.size(); k++) {//到非MST中的顶点 if (originalGraph.getMark(S.get(j)) == GraphMatrix.VISITED && originalGraph.getMark(N.get(k)) == GraphMatrix.UNVISITED && originalGraph.getWeight(S.get(j), N.get(k)) < miniWeight) { //只需要看从已访问结点到未访问结点的边 miniWeight = originalGraph.getWeight(S.get(j), N.get(k)); v1 = S.get(j); v2 = N.get(k); } } } System.out.println(originalGraph.getVertexValue(v1) + "-" + miniWeight + "->" + originalGraph.getVertexValue(v2)); //更新 S.add(v2);//加入MST N.remove((Object) v2);//同时从N中移除 originalGraph.setMark(v2, GraphMatrix.VISITED); } } public static void main(String[] args) { //定义图的所有顶点 String[] vertexs = {"A", "B", "C", "D", "E", "F"}; //创建图 GraphMatrix graph = new GraphMatrix(vertexs.length); //添加顶点到图中 for (String vertex : vertexs) { graph.insertVertex(vertex); } //添加边到图中 graph.insertEdge(0, 2, 7); graph.insertEdge(0, 4, 9); graph.insertEdge(1, 2, 5); graph.insertEdge(1, 5, 6); graph.insertEdge(2, 3, 1); graph.insertEdge(2, 5, 2); graph.insertEdge(3, 5, 2); graph.insertEdge(4, 5, 1); Prim test = new Prim(); test.createOriginalGraph(graph); test.showOriginalGraph(); test.prim(0); }}
[1000, 1000, 7, 1000, 9, 1000][1000, 1000, 5, 1000, 1000, 6][7, 5, 1000, 1, 1000, 2][1000, 1000, 1, 1000, 1000, 2][9, 1000, 1000, 1000, 1000, 1][1000, 6, 2, 2, 1, 1000]A-7->CC-1->DC-2->FF-1->EC-5->B
Kruskal算法——从边出发 算法步骤
1️⃣设连通网 N = (V, E )，令最小生成树初始状态为只有 n 个顶点而无边的非连通图 T=(V, { })，每个顶点自成一个连通分量。
2️⃣在 E 中选取代价最小的边，若该边依附 的顶点落在 T 中不同的连通分量上（即： 不能形成环），则将此边加入到 T 中；否 则，舍去此边，选取下一条代价最小的边。
3️⃣ 依此类推，直至 T 中所有顶点都在同一 连通分量上为止。
示例 代码实现
1️⃣ 利用并查集树判断结点是否连通，以及连通两个非连通分量
public class GTNodeA { private int parent;//父结点下标 private Object element;//存储元素内容 public GTNodeA() { this(null, -1); } public GTNodeA(Object element) { this(element, -1); } public GTNodeA(Object element, int parent) { this.element = element; this.parent = parent; } public int getParent() { return parent; } public int setParent(int parent) { return this.parent = parent; } public Object getElement() { return element; } public void setElement(Object element) { this.element = element; }}public class UnionFindTree { //用树实现并查集 public GTNodeA[] set; public UnionFindTree(GTNodeA[] set) { this.set = set; } public int find(int i) { GTNodeA current = set[i]; if (current.getParent()<0) return i; return current.setParent(find(current.getParent())); }//使用路劲压缩法：在查找某个元素是否属于某个集合时，将该结点到根结点路径上 // 所有结点的父指针全部改为指向根结点，这种方式可以产生极浅的树 public void union(int i, int j) { int root1 = find(i); int num1 = set[root1].getParent(); int root2 = find(j); int num2 = set[root2].getParent(); if (num1 <= num2) { set[root1].setParent(num1+num2); set[root2].setParent(root1); //将其中结点数少的一棵树的根结点的父结点设置为 //结点数多的一棵树的根结点 } else { set[root2].setParent(num1+num2); set[root1].setParent(root2); //将其中结点数少的一棵树的根结点的父结点设置为 //结点数多的一棵树的根结点 } }//使用了重量平衡原则 public boolean isConnected(int i,int j){ return find(i)==find(j); } public void print() { for (int i = 0; i < set.length; i++) { System.out.print(set[i].getElement() + " "); } } public static void main(String[] args) { GTNodeA node_A = new GTNodeA("A"); GTNodeA node_C = new GTNodeA("C"); GTNodeA node_H = new GTNodeA("H"); GTNodeA node_K = new GTNodeA("K"); GTNodeA node_E = new GTNodeA("E"); GTNodeA node_B = new GTNodeA("B"); GTNodeA node_D = new GTNodeA("D"); GTNodeA node_F = new GTNodeA("F"); GTNodeA node_J = new GTNodeA("J"); GTNodeA node_L = new GTNodeA("L"); GTNodeA node_N = new GTNodeA("N"); GTNodeA node_M = new GTNodeA("M"); GTNodeA node_I = new GTNodeA("I"); GTNodeA node_G = new GTNodeA("G"); GTNodeA[] test = {node_A, node_B, node_C, node_D, node_E, node_F, node_G, node_H, node_I, node_J, node_K, node_L, node_M, node_N}; UnionFindTree testTree = new UnionFindTree(test); System.out.print("initialized forest: "); testTree.print(); System.out.println(); System.out.println("find(1): " + testTree.find(1)); System.out.println("find(3): " + testTree.find(3)); System.out.println("find(4): " + testTree.find(4)); testTree.union(0, 4); testTree.union(0, 1); testTree.union(0, 3); System.out.println("union(0,4), union(0,1), union(0,3)"); System.out.println("find(1): " + testTree.find(1)); System.out.println("find(3): " + testTree.find(3)); System.out.println("find(4): " + testTree.find(4)); }}
2️⃣ 利用最小优先队列优化边的查找与删除
public class Edge implements Comparable { private int v1;//起点 private int v2;//终点 private int weight;//权重 public Edge(int v1, int v2) { this.v1 = v1; this.v2 = v2; } public Edge(int v1, int v2, int weight) { this.v1 = v1; this.v2 = v2; this.weight = weight; } public int getV1() { return v1; } public void setV1(int v1) { this.v1 = v1; } public int getV2() { return v2; } public void setV2(int v2) { this.v2 = v2; } public int getWeight() { return weight; } public void setWeight(int weight) { this.weight = weight; } @Override public int compareTo(@NotNull Edge edge) { if (this.weight < edge.weight) { return -1; } else if (this.weight == edge.weight) { return 0; } else { return 1; } } @Override public String toString() { return "Edge{" + v1 + "->" + v2 + " weight=" + weight + '}'; }}public class MinPriorityQueue> { //最小优先队列 private static final int DEFAULT_CAPACITY = 10;//默认大小 private int currentSize;//当前堆的大小 private T[] array;//堆数组 public MinPriorityQueue() { this.array = (T[]) new Comparable[DEFAULT_CAPACITY + 1]; currentSize = 0; } public MinPriorityQueue(int size) { this.array = (T[]) new Comparable[size + 1]; currentSize = 0; } public MinPriorityQueue(T[] array) { this.array = (T[]) new Comparable[array.length + 1]; for (int i = 0; i < array.length; i++) { this.array[i + 1] = array[i]; }//从1开始算 currentSize = array.length; buildHeap(); } public void insert(T element) { try { if (isFull()) { throw new Exception("Array is full!"); } int temp = ++currentSize; array[temp] = element;//将element放在数组最后 while ((temp != 1) && (array[temp].compareTo(array[getParent(temp)]) < 0)) { swap(array, temp, getParent(temp)); temp = getParent(temp);//如果比父结点的值小则于其交换 }//注意根结点的下标为1，不是0 } catch (Exception e) { e.printStackTrace(); } } public T findMin() { return array[1]; } public void deleteMin() { try { if (isEmpty()) { throw new Exception("Array is empty!"); } else { swap(array, 1, currentSize--);//将堆顶元素放到最后,同时删除 if (currentSize != 0) siftDown(1); } } catch (Exception e) { e.printStackTrace(); } } private void siftDown(int pos) { try { if (pos < 0 || pos > currentSize) { throw new Exception("Illegal position!"); } while (!isLeaf(pos)) { int j = getLeft(pos); if ((j < currentSize) && (array[j].compareTo(array[j + 1])) > 0) j++; //跟子树中最小的值交换 if (array[pos].compareTo(array[j]) < 0) return; //当前值已经比子树中的值都小，则返回 swap(array, pos, j);//交换 pos = j; } } catch (Exception e) { e.printStackTrace(); } } public void print() { for (int i = 1; i <= currentSize; i++) { System.out.print(array[i] + " "); } } public void heapSort() { while (currentSize != 0) { System.out.print(findMin() + " "); deleteMin(); } } public boolean isEmpty() { return currentSize == 0; } public boolean isFull() { return currentSize == array.length - 1; } private boolean isLeaf(int i) { return i > currentSize / 2; } private void buildHeap() { for (int i = currentSize / 2; i > 0; i--) { siftDown(i);//对每个非叶子结点进行下沉操作 //从右到左，从下到上 } } private int getLeft(int i) { return 2 * i; } private int getRight(int i) { return 2 * i + 1; } private int getParent(int i) { return i / 2; } private void swap(T[] array, int x, int y) { T temp = array[y]; array[y] = array[x]; array[x] = temp; return; } public static void main(String[] args) throws Exception { Edge edge1 = new Edge(1, 2, 1); Edge edge2 = new Edge(1, 2, 2); Edge edge3 = new Edge(1, 2, 6); Edge edge4 = new Edge(1, 2, 4); Edge edge5 = new Edge(1, 2, 5); Edge edge6 = new Edge(1, 2, 7); Edge edge7 = new Edge(1, 2, 3);// Integer[] elements = {1, 2, 6, 4, 5, 7, 3};// MinPriorityQueue test = new MinPriorityQueue(elements); Edge[] edges = {edge1, edge2, edge3, edge4, edge5, edge6, edge7}; MinPriorityQueue test = new MinPriorityQueue(edges); test.print(); System.out.println(); test.heapSort(); System.out.println(); test.print(); }}
3️⃣ 算法具体实现
public class Kruskal { private ArrayList MST;//最小生成树中的所有边 private UnionFindTree ufTree;//并查集树，放索引 private MinPriorityQueue allEdges;//图中所有的边 private GraphMatrix originalGraph;//用相邻矩阵实现的原图 private int vertexNum;//结点数 public Kruskal(GraphMatrix originalGraph) { this.originalGraph = originalGraph; this.vertexNum = originalGraph.getVertexNum(); } public void generateMST() { this.MST = new ArrayList();//初始化MST GTNodeA[] nodes = new GTNodeA[vertexNum]; for (int i = 0; i < vertexNum; i++) { nodes[i] = new GTNodeA(i); } this.ufTree = new UnionFindTree(nodes);//初始化并查集 this.allEdges = new MinPriorityQueue<>(originalGraph.getEdgeNum());//初始化优先队列 for (int i = 0; i < vertexNum; i++) { for (int j = i + 1; j < vertexNum; j++) { if (originalGraph.getWeight(i, j) != GraphMatrix.UNCONNECTED) { allEdges.insert(new Edge(i, j, originalGraph.getWeight(i, j))); } } }//将所有的边加入优先队列中 while (!allEdges.isEmpty() && MST.size() < vertexNum - 1) { Edge e = allEdges.findMin(); allEdges.deleteMin(); int v1 = e.getV1(); int v2 = e.getV2(); //判断v1和v2是否已经连通 if (ufTree.isConnected(v1, v2)) continue; ufTree.union(v1, v2);//不连通则连接 MST.add(e);//将边并入MST } } public ArrayList getMST() { return MST; } public void printMST() { for (Edge edge : MST) { System.out.println(originalGraph.getVertexValue(edge.getV1()) + "-" + originalGraph.getWeight(edge.getV1(), edge.getV2()) + "->" + originalGraph.getVertexValue(edge.getV2())); } } public static void main(String[] args) { String[] vertexs = {"A", "B", "C", "D", "E", "F"}; //创建图 GraphMatrix graph = new GraphMatrix(vertexs.length); //添加顶点到图中 for (String vertex : vertexs) { graph.insertVertex(vertex); } //添加边到图中 graph.insertEdge(0, 2, 7); graph.insertEdge(0, 4, 9); graph.insertEdge(1, 2, 5); graph.insertEdge(1, 5, 6); graph.insertEdge(2, 3, 1); graph.insertEdge(2, 5, 2); graph.insertEdge(3, 5, 2); graph.insertEdge(4, 5, 1); Kruskal test = new Kruskal(graph); test.generateMST(); test.printMST(); }}
C-1->DE-1->FC-2->FB-5->CA-7->C