![[XJTUSE]数据结构学习——4.4 最小支撑树(完整代码实现——java）](http://www.mshxw.com/aiimages/31/737496.png "[XJTUSE]数据结构学习——4.4 最小支撑树(完整代码实现——java）")
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的一条边
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->C C-1->D C-2->F F-1->E C-5->BKruskal算法——从边出发 算法步骤
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->D E-1->F C-2->F B-5->C A-7->C
