Java求最小生成樹的兩種算法詳解
更新時間：2022年01月25日 15:34:03 作者：劉Java
最小生成樹（Minimum Spanning Tree）：在連通圖的所有生成樹中，所有邊的權(quán)值和最小的生成樹，稱為最小生成樹。這篇文章主要介紹了求最小生成樹的兩種方法：Prim算法和Kruskal算法，需要的可以參考一下
介紹了圖的最小生成樹的概念，然后介紹了求最小生成樹的兩種算法：Prim算法和Kruskal算法的原理，最后提供了基于鄰接矩陣和鄰接鏈表的圖對兩種算法的Java實現(xiàn)。
閱讀本文需要一定的圖的基礎(chǔ)，如果對于圖不是太明白的可以看看這篇文章：Java數(shù)據(jù)結(jié)構(gòu)之圖的原理與實現(xiàn)。
1 最小生成樹的概述
生成樹（SpanningTree）：一個連通圖的生成樹是指一個連通子圖，它含有圖中全部n個頂點，但只有足以構(gòu)成一棵樹的n-1條邊。一顆有n個頂點的生成樹有且僅有n-1條邊，如果生成樹中再添加一條邊，則必定成環(huán)。
最小生成樹（Minimum Spanning Tree）：在連通圖的所有生成樹中，所有邊的權(quán)值和最小的生成樹，稱為最小生成樹。
在生活中，圖形結(jié)構(gòu)的應(yīng)用是最廣泛的。比如常見的通信網(wǎng)絡(luò)搭建路線選擇，村莊可以看作頂點，村莊之間如果有通信路徑，則算作兩點之間的邊或者弧，兩個村莊之間的通信成本，可以看作邊或者弧的權(quán)值。
上圖就是生活中通信網(wǎng)絡(luò)搭建路線的選擇映射到圖形結(jié)構(gòu)的案例。頂點作為村莊，村莊之間如果有通信路徑則擁有邊，村莊的之間的通信搭建成本則是邊的權(quán)值。
一種很常見的需求是要求對于能夠通信的村莊都必須通信，并且通信建設(shè)成本和最小，畢竟經(jīng)費“有限”，省下來的經(jīng)費，嘿嘿！
上面的問題，轉(zhuǎn)換為數(shù)學模型，就是求一個圖的最小生成樹的問題，即：選出一條路線，連通了所有能夠連通頂點，并且權(quán)值和最小。這樣的問題已經(jīng)有了很多種解法，最經(jīng)典的有兩種算法，普里姆（Prim）算法和克魯斯卡爾（Kruskal)算法。
2 普里姆算法（Prim）
2.1 原理
普里姆（Prim）算法是以某頂點為起點，假設(shè)所有頂點均未連接，逐步找各頂點上最小權(quán)值的邊來連接并構(gòu)建最小生成樹。是以點為目標去構(gòu)建最小生成樹。
具體的步驟是： 首先隨機選取一個頂點a，尋找頂點a可連接所有的頂點，選擇一個權(quán)值低的頂點進行連接；然后尋找與這兩個頂點或可連接的所有頂點，選擇一個權(quán)值低的頂點與其中一個頂點進行連接；如此往復(fù)n-1次，每次選擇距離任意一個已連接末端頂點最短的頂點（而不是距離首個頂點最短的頂點）進行連接，直到所有的頂點都進行連接，至此最小生成樹構(gòu)建完畢。
2.2 案例分析
該案例對應(yīng)著下面實現(xiàn)代碼中的案例。
在上面的圖中，首先選擇頂點A作為已連接點，尋找頂點A可連接所有的頂點C、D、F，選擇一個權(quán)值低的頂點進行連接，這里選擇A-C；
然后尋找與A或C可連接的所有頂點（排除已連接的點），找到B、D、F，一共有4條邊可選，A-D、A-F、C-B、C-D，選擇一個權(quán)值低的頂點與其中一個頂點進行連接，這里明顯選擇A-D連接；
然后尋找與A或C或D可連接的所有頂點（排除已連接的點），找到B、F，一共有3條邊可選，C-B、D-B、A-F，選擇一個權(quán)值低的頂點與其中一個頂點進行連接，這里明顯選擇A-F連接；
然后尋找與A或C或D或F可連接的所有頂點（排除已連接的點），找到B、G，一共有3條邊可選，C-B、D-B、F-G，選擇一個權(quán)值低的頂點與其中一個頂點進行連接，這里明顯選擇C-B連接；
然后尋找與A或C或D或F或B可連接的所有頂點（排除已連接的點），找到E、G，一共有2條邊可選，B-E、F-G，選擇一個權(quán)值低的頂點與其中一個頂點進行連接，這里明顯選擇B-E連接；
然后尋找與A或C或D或F或B或E可連接的所有頂點（排除已連接的點），找到G，一共有2條邊可選，E-G、F-G，選擇一個權(quán)值低的頂點與其中一個頂點進行連接，這里明顯選擇E-G連接；
所有的頂點連接完畢，此時最小生成樹已經(jīng)構(gòu)建好了，最小權(quán)值為23。
3 克魯斯卡爾算法（Kruskal）
3.1 原理
克魯斯卡爾算法（Kruskal）根據(jù)邊的權(quán)值以遞增的方式逐漸建立最小生成樹，是以邊為目標去構(gòu)建最小生成樹。
具體的步驟是： 將加權(quán)圖每個頂點都看做森林，然后將圖中每條鄰接邊的權(quán)值按照升序的方式進行排列，接著從排列好的鄰接邊表中抽取權(quán)值最小的邊，寫入該邊的起始頂點和結(jié)束頂點，連接頂點將森林構(gòu)成樹，然后讀取起始結(jié)束頂點的鄰接邊，優(yōu)先抽取權(quán)值小的鄰接邊，繼續(xù)連接頂點將森林構(gòu)成樹。添加鄰接邊的要求是加入到圖中的鄰接邊不構(gòu)成回路（環(huán)）。如此反復(fù)進行，直到已經(jīng)添加n-1條邊為止。至此最小生成樹構(gòu)建完畢。
3.2 案例分析
該案例對應(yīng)著下面實現(xiàn)代碼中的案例，傳統(tǒng)Kruskal算法過程如下：
首先獲取邊集數(shù)組并按照權(quán)值重小到大進行排序，在代碼中的排序本人直接使用的sort排序，也可以自己實現(xiàn)堆排序，排序后結(jié)果如下：
Edge{from=A, to=C, weight=1}
Edge{from=D, to=A, weight=2}
Edge{from=A, to=F, weight=3}
Edge{from=B, to=C, weight=4}
Edge{from=C, to=D, weight=5}
Edge{from=E, to=G, weight=6}
Edge{from=E, to=B, weight=7}
Edge{from=D, to=B, weight=8}
Edge{from=F, to=G, weight=9}
循環(huán)取出第1條邊A-C，判斷與已經(jīng)找到的最小生成樹不會形成環(huán)，權(quán)值總和增加1，繼續(xù)；
循環(huán)取出第2條邊D-A，判斷與已經(jīng)找到的最小生成樹不會形成環(huán)，權(quán)值總和增加2，繼續(xù)；
循環(huán)取出第3條邊A-F，判斷與已經(jīng)找到的最小生成樹不會形成環(huán)，權(quán)值總和增加3，繼續(xù)；
循環(huán)取出第4條邊B-C，判斷與已經(jīng)找到的最小生成樹不會形成環(huán)，權(quán)值總和增加4，繼續(xù)；
循環(huán)取出第5條邊C-D，判斷與已經(jīng)找到的最小生成樹會形成環(huán)，該條邊丟棄，繼續(xù)；
循環(huán)取出第6條邊E-G，判斷與已經(jīng)找到的最小生成樹不會形成環(huán)，權(quán)值總和增加6，繼續(xù)；
循環(huán)取出第7條邊E-B，判斷與已經(jīng)找到的最小生成樹不會形成環(huán)，權(quán)值總和增加7，繼續(xù)；
循環(huán)取出第8條邊D-B，判斷與已經(jīng)找到的最小生成樹會形成環(huán)，該條邊丟棄，繼續(xù)；
循環(huán)取出第9條邊F-G，判斷與已經(jīng)找到的最小生成樹會形成環(huán)，該條邊丟棄，繼續(xù)；
此時循環(huán)結(jié)束，那么最小生成樹也已經(jīng)找到了，最小生成樹的權(quán)值總和為23。
上面步驟中，判斷是否形成環(huán)很關(guān)鍵，通常的做法是，對已經(jīng)找到的最小生成樹的頂點進行排序（從起點到終點)，然后每新添加一條邊，就使用新添加邊的起點和終點取最小二叉樹中尋找，排序后的終點，找到的終點一致，則說明最小生成樹加上這條邊就會形成環(huán)，否則說明不會，那么更新排序的終點。
4 鄰接矩陣加權(quán)圖實現(xiàn)
這里的實現(xiàn)能夠構(gòu)造一個基于鄰接矩陣實現(xiàn)無向加權(quán)圖的類，并且提供深度優(yōu)先遍歷和廣度優(yōu)先遍歷的方法，提供獲取邊集數(shù)組的方法，提供Prim和Kruskal兩種求最小生成樹的方法。
/**
* 無向加權(quán)圖鄰接矩陣實現(xiàn)
* {@link MatrixPrimAndKruskal#MatrixPrimAndKruskal(E[], Edge[])} 構(gòu)建無向加權(quán)圖
* {@link MatrixPrimAndKruskal#DFS()} 深度優(yōu)先遍歷無向加權(quán)圖
* {@link MatrixPrimAndKruskal#BFS()} 廣度優(yōu)先遍歷無向加權(quán)圖
* {@link MatrixPrimAndKruskal#toString()} 輸出無向加權(quán)圖
* {@link MatrixPrimAndKruskal#prim()} Prim算法實現(xiàn)最小生成樹
* {@link MatrixPrimAndKruskal#kruskal()} Kruskal算法實現(xiàn)最小生成樹
* {@link MatrixPrimAndKruskal#kruskalAndPrim()} Kruskal算法結(jié)合Prim算法實現(xiàn)最小生成樹
* {@link MatrixPrimAndKruskal#getEdges()} 獲取邊集數(shù)組
*
* @author lx
* @date 2020/5/14 18:13
*/
public class MatrixPrimAndKruskal<E> {
/**
* 頂點數(shù)組
*/
private Object[] vertexs;
/**
* 鄰接矩陣
*/
private int[][] matrix;
/**
*
*/
private Edge<E>[] edges;
/**
* 由于是加權(quán)圖,這里設(shè)置一個邊的權(quán)值上限,任何邊的最大權(quán)值不能大于等于該值，在實際應(yīng)用中，該值應(yīng)該根據(jù)實際情況確定
*/
private static final int NO_EDGE = 99;
/**
* 邊對象,具有權(quán)值,在構(gòu)建加權(quán)無向圖時使用
*/
private static class Edge<E> {
private E from;
private E to;
private int weight;
public Edge(E from, E to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
@Override
public String toString() {
return "Edge{" +
"from=" + from +
", to=" + to +
", weight=" + weight +
'}';
}
}
/**
* 創(chuàng)建無向加權(quán)圖
*
* @param vertexs 頂點數(shù)組
* @param edges 邊對象數(shù)組
*/
public MatrixPrimAndKruskal(Object[] vertexs, Edge<E>[] edges) {
//初始化邊數(shù)組
this.edges = edges;
// 初始化頂點數(shù)組,并添加頂點
this.vertexs = Arrays.copyOf(vertexs, vertexs.length);
// 初始化邊矩陣,并預(yù)先填充邊信息
this.matrix = new int[vertexs.length][vertexs.length];
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
if (i == j) {
this.matrix[i][j] = 0;
} else {
this.matrix[i][j] = NO_EDGE;
}
}
}
for (Edge<E> edge : edges) {
// 讀取一條邊的起始頂點和結(jié)束頂點索引值
int p1 = getPosition(edge.from);
int p2 = getPosition(edge.to);
//對稱的兩個點位都置為edge.weight,無向圖可以看作相互可達的有向圖
this.matrix[p1][p2] = edge.weight;
this.matrix[p2][p1] = edge.weight;
}
}
/**
* 獲取某條邊的某個頂點所在頂點數(shù)組的索引位置
*
* @param e 頂點的值
* @return 所在頂點數(shù)組的索引位置, 或者-1 - 表示不存在
*/
private int getPosition(E e) {
for (int i = 0; i < vertexs.length; i++) {
if (vertexs[i] == e) {
return i;
}
}
return -1;
}
/**
* 深度優(yōu)先搜索遍歷圖,類似于樹的前序遍歷,
*/
public void DFS() {
//新建頂點訪問標記數(shù)組,對應(yīng)每個索引對應(yīng)相同索引的頂點數(shù)組中的頂點
boolean[] visited = new boolean[vertexs.length];
//初始化所有頂點都沒有被訪問
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("DFS: ");
for (int i = 0; i < vertexs.length; i++) {
if (!visited[i]) {
DFS(i, visited);
}
}
System.out.println();
}
/**
* 深度優(yōu)先搜索遍歷圖的遞歸實現(xiàn),類似于樹的先序遍歷
* 因此模仿樹的先序遍歷,同樣借用棧結(jié)構(gòu),這里使用的是方法的遞歸,隱式的借用棧
*
* @param i 頂點索引
* @param visited 訪問標志數(shù)組
*/
private void DFS(int i, boolean[] visited) {
visited[i] = true;
System.out.print(vertexs[i] + " ");
// 遍歷該頂點的所有鄰接點。若該鄰接點是沒有訪問過，那么繼續(xù)遞歸遍歷領(lǐng)接點
for (int w = firstVertex(i); w >= 0; w = nextVertex(i, w)) {
if (!visited[w]) {
DFS(w, visited);
}
}
}
/**
* 廣度優(yōu)先搜索圖,類似于樹的層序遍歷
* 因此模仿樹的層序遍歷,同樣借用隊列結(jié)構(gòu)
*/
public void BFS() {
// 輔組隊列
Queue<Integer> indexLinkedList = new LinkedList<>();
//新建頂點訪問標記數(shù)組,對應(yīng)每個索引對應(yīng)相同索引的頂點數(shù)組中的頂點
boolean[] visited = new boolean[vertexs.length];
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("BFS: ");
for (int i = 0; i < vertexs.length; i++) {
if (!visited[i]) {
visited[i] = true;
System.out.print(vertexs[i] + " ");
indexLinkedList.add(i);
}
if (!indexLinkedList.isEmpty()) {
//j索引出隊列
Integer j = indexLinkedList.poll();
//繼續(xù)訪問j的鄰接點
for (int k = firstVertex(j); k >= 0; k = nextVertex(j, k)) {
if (!visited[k]) {
visited[k] = true;
System.out.print(vertexs[k] + " ");
//繼續(xù)入隊列
indexLinkedList.add(k);
}
}
}
}
System.out.println();
}
/**
* 返回頂點v的第一個鄰接頂點的索引，失敗則返回-1
*
* @param v 頂點v在數(shù)組中的索引
* @return 返回頂點v的第一個鄰接頂點的索引，失敗則返回-1
*/
private int firstVertex(int v) {
//如果索引超出范圍,則返回-1
if (v < 0 || v > (vertexs.length - 1)) {
return -1;
}
/*根據(jù)鄰接矩陣的規(guī)律:頂點索引v對應(yīng)著邊二維矩陣的matrix[v][i]一行記錄
* 從i=0開始*/
for (int i = 0; i < vertexs.length; i++) {
if (matrix[v][i] != 0 && matrix[v][i] != NO_EDGE) {
return i;
}
}
return -1;
}
/**
* 返回頂點v相對于w的下一個鄰接頂點的索引，失敗則返回-1
*
* @param v 頂點索引
* @param w 第一個鄰接點索引
* @return 返回頂點v相對于w的下一個鄰接頂點的索引，失敗則返回-1
*/
private int nextVertex(int v, int w) {
//如果索引超出范圍,則返回-1
if (v < 0 || v > (vertexs.length - 1) || w < 0 || w > (vertexs.length - 1)) {
return -1;
}
/*根據(jù)鄰接矩陣的規(guī)律:頂點索引v對應(yīng)著邊二維矩陣的matrix[v][i]一行記錄
* 由于鄰接點w的索引已經(jīng)獲取了,所以從i=w+1開始尋找*/
for (int i = w + 1; i < vertexs.length; i++) {
if (matrix[v][i] != 0 && matrix[v][i] != NO_EDGE) {
return i;
}
}
return -1;
}
/**
* 輸出圖
*
* @return 輸出圖字符串
*/
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
stringBuilder.append(matrix[i][j]).append("\t");
}
stringBuilder.append("\n");
}
return stringBuilder.toString();
}
/**
* Prim算法求最小生成樹
*/
public void prim() {
System.out.println("prim: ");
//對應(yīng)節(jié)點應(yīng)該被連接的前驅(qū)節(jié)點,用來輸出
//默認為0,即前驅(qū)結(jié)點為第一個節(jié)點
int[] mid = new int[matrix.length];
//如果某頂點作為末端頂點被連接，對應(yīng)位置應(yīng)該為true
//第一個頂點默認被連接
boolean[] connected = new boolean[matrix.length];
connected[0] = true;
//存儲未連接頂點到已連接頂點的最短距離(最小權(quán))
int[] dis = new int[matrix.length];
//首先將矩陣第一行即其他頂點到0索引頂點的權(quán)值拷貝進去
System.arraycopy(matrix[0], 0, dis, 0, matrix.length);
//存儲路徑長度
int sum = 0;
//最小權(quán)值
int min;
/*默認第一個頂點已經(jīng)找到了,因此最多還要需要大循環(huán)n-1次*/
for (int k = 1; k < matrix.length; k++) {
min = NO_EDGE;
//最小權(quán)值的頂點的索引
int minIndex = 0;
/*尋找權(quán)值最小的且未被連接的頂點索引*/
for (int i = 1; i < matrix.length; i++) {
//排除已連接的頂點,排除權(quán)值等于0的值,這里權(quán)值等于0表示已生成的最小生成樹的頂點都未能與該頂點連接
if (!connected[i] && dis[i] != 0 && dis[i] < min) {
min = dis[i];
minIndex = i;
}
}
//如果沒找到,那么該圖可能不是連通圖,直接返回了,此時最小生成樹沒啥意義
if (minIndex == 0) {
return;
}
//權(quán)值和增加
sum += min;
//該新連接頂點對應(yīng)的索引值變成true,表示已被連接,后續(xù)判斷時跳過該頂點
connected[minIndex] = true;
//輸出對應(yīng)的前驅(qū)頂點到該最小頂點的權(quán)值
System.out.println(vertexs[mid[minIndex]] + " ---> " + vertexs[minIndex] + " 權(quán)值:" + min);
/*在新頂點minIndex加入之前的其他所有頂點到連接頂點最小的權(quán)值已經(jīng)計算過了
因此只需要更新其他未連接頂點到新連接頂點minIndex是否還有更短的權(quán)值,有的話就更新找到距離已連接的頂點權(quán)最小的頂點*/
for (int i = 1; i < matrix.length; i++) {
//如果該頂點未連接
if (!connected[i]) {
/*如果新頂點到未連接頂點i的權(quán)值不為0,并且比原始頂點到未連接頂點i的權(quán)值還要小,那么更新對應(yīng)位置的最小權(quán)值*/
if (matrix[minIndex][i] != 0 && dis[i] > matrix[minIndex][i]) {
//更新最小權(quán)值
dis[i] = matrix[minIndex][i];
//更新前驅(qū)節(jié)點索引為新加入節(jié)點索引
mid[i] = minIndex;
}
}
}
}
System.out.println("sum: " + sum);
}
/**
* Kruskal算法求最小生成樹傳統(tǒng)實現(xiàn),要求知道邊集數(shù)組,和頂點數(shù)組
*/
public void kruskal() {
System.out.println("Kruskal: ");
//由于創(chuàng)建圖的時候保存了邊集數(shù)組,這里直接使用就行了
//Edge[] edges = getEdges();
//this.edges=edges;
//對邊集數(shù)組進行排序
Arrays.sort(this.edges, Comparator.comparingInt(o -> o.weight));
// 用于保存已有最小生成樹中每個頂點在該最小樹中的最終終點的索引
int[] vends = new int[this.edges.length];
//能夠知道終點索引范圍是[0,this.edges.length-1],因此填充edges.length表示沒有終點
Arrays.fill(vends, this.edges.length);
int sum = 0;
for (Edge<E> edge : this.edges) {
// 獲取第i條邊的起點索引from
int from = getPosition(edge.from);
// 獲取第i條邊的終點索引to
int to = getPosition(edge.to);
// 獲取頂點from在"已有的最小生成樹"中的終點
int m = getEndIndex(vends, from);
// 獲取頂點to在"已有的最小生成樹"中的終點
int n = getEndIndex(vends, to);
// 如果m!=n，意味著沒有形成環(huán)路,則可以添加,否則直接跳過,進行下一條邊的判斷
if (m != n) {
//添加設(shè)置原始終點索引m在已有的最小生成樹中的終點為n
vends[m] = n;
System.out.println(vertexs[from] + " ---> " + vertexs[to] + " 權(quán)值:" + edge.weight);
sum += edge.weight;
}
}
System.out.println("sum: " + sum);
//System.out.println(Arrays.toString(this.edges));
}
/**
* 獲取頂點索引i的終點如果沒有終點則返回頂點索引本身
*
* @param vends 頂點在最小生成樹中的終點
* @param i 頂點索引
* @return 頂點索引i的終點如果沒有終點則返回頂點索引本身
*/
private int getEndIndex(int[] vends, int i) {
//這里使用循環(huán)查找的邏輯,尋找的是最終的終點
while (vends[i] != this.edges.length) {
i = vends[i];
}
return i;
}
/**
* 如果沒有現(xiàn)成的邊集數(shù)組，那么根據(jù)鄰接矩陣結(jié)構(gòu)獲取圖中的邊集數(shù)組
*
* @return 圖的邊集數(shù)組
*/
private Edge[] getEdges() {
List<Edge> edges = new ArrayList<>();
/*遍歷矩陣數(shù)組 只需要遍歷一半就行了*/
for (int i = 0; i < vertexs.length; i++) {
for (int j = i + 1; j < vertexs.length; j++) {
//如果存在邊
if (matrix[i][j] != NO_EDGE && matrix[i][j] != 0) {
edges.add(new Edge<>(vertexs[i], vertexs[j], matrix[i][j]));
//edges[index++] = new Edge(vertexs[i], vertexs[j], matrix[i][j]);
}
}
}
return edges.toArray(new Edge[0]);
}
/**
* Kruskal結(jié)合Prim算法.不需要知道邊集,只需要矩陣數(shù)組,和頂點數(shù)組
* 同樣是求最小權(quán)值的邊,但是有一個默認起點頂點,該起點可以是要求[0,頂點數(shù)量-1]之間的任意值，同時查找最小權(quán)的邊。
* 可能會有Bug,目前未發(fā)現(xiàn)
*/
public void kruskalAndPrim() {
System.out.println("kruskalAndPrim: ");
//已經(jīng)找到的邊攜帶的頂點對應(yīng)的索引將變?yōu)閠rue,其余未找到邊對應(yīng)的頂點將是false
boolean[] connected = new boolean[matrix.length];
//這里選擇第一個頂點為起點,表示以該頂點開始尋找包含該頂點的最小邊
connected[0] = true;
int sum = 0, n1 = 0, n2 = 0;
//最小權(quán)值
int min;
while (true) {
min = NO_EDGE;
/*找出所有帶有已找到頂點的邊中,最小權(quán)值的邊,只需要尋找對稱矩陣的一半即可*/
//第一維
for (int i = 0; i < matrix.length; i++) {
//第二維
for (int j = i + 1; j < matrix.length; j++) {
//排除等于0的,排除兩個頂點都找到了的,這里實際上已經(jīng)隱含了排除環(huán)的邏輯,如果某條邊的兩個頂點都找到了,那么如果算上該條邊,肯定會形成環(huán)
//尋找剩下的最小的權(quán)值的邊
if (matrix[i][j] != 0 && connected[i] != connected[j] && matrix[i][j] < min) {
min = matrix[i][j];
n1 = i;
n2 = j;
}
}
}
//如果沒找到最小權(quán)值,該圖可能不是連通圖,或者已經(jīng)尋找完畢,直接返回
if (min == NO_EDGE) {
System.out.println(" sum:" + sum);
return;
}
//已經(jīng)找到的邊對應(yīng)的兩個頂點都置為true
connected[n1] = true;
connected[n2] = true;
//輸出找到的邊和最小權(quán)值
System.out.println(vertexs[n1] + " ---> " + vertexs[n2] + " 權(quán)值:" + min);
sum += min;
}
}
public static void main(String[] args) {
//頂點數(shù)組
Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
//邊數(shù)組,加權(quán)值
Edge[] edges = {
new Edge<>('A', 'C', 1),
new Edge<>('D', 'A', 2),
new Edge<>('A', 'F', 3),
new Edge<>('B', 'C', 4),
new Edge<>('C', 'D', 5),
new Edge<>('E', 'G', 6),
new Edge<>('E', 'B', 7),
new Edge<>('D', 'B', 8),
new Edge<>('F', 'G', 9)};
//構(gòu)建圖
MatrixPrimAndKruskal<Character> matrixPrimAndKruskal = new MatrixPrimAndKruskal<Character>(vexs, edges);
//輸出圖
System.out.println(matrixPrimAndKruskal);
//深度優(yōu)先遍歷
matrixPrimAndKruskal.DFS();
//廣度優(yōu)先遍歷
matrixPrimAndKruskal.BFS();
//Prim算法輸出最小生成樹
matrixPrimAndKruskal.prim();
//Kruskal算法輸出最小生成樹
matrixPrimAndKruskal.kruskal();
//Kruskal算法結(jié)合Prim算法輸出最小生成樹,可能會有Bug,目前未發(fā)現(xiàn)
matrixPrimAndKruskal.kruskalAndPrim();
//獲取邊集數(shù)組
Edge[] edges1 = matrixPrimAndKruskal.getEdges();
System.out.println(Arrays.toString(edges1));
}
}5 鄰接表加權(quán)圖實現(xiàn)
這里的實現(xiàn)能夠構(gòu)造一個基于鄰接表實現(xiàn)無向加權(quán)圖的類；并且提供深度優(yōu)先遍歷和廣度優(yōu)先遍歷的方法，提供獲取邊集數(shù)組的方法，提供Prim和Kruskal兩種求最小生成樹的方法。
/**
* 無向加權(quán)圖鄰接表實現(xiàn)
* {@link ListPrimAndKruskal#ListPrimAndKruskal(E[], Edge[])} 構(gòu)建無向加權(quán)圖
* {@link ListPrimAndKruskal#DFS()} 深度優(yōu)先遍歷無向加權(quán)圖
* {@link ListPrimAndKruskal#BFS()} 廣度優(yōu)先遍歷無向加權(quán)圖
* {@link ListPrimAndKruskal#toString()} 輸出無向加權(quán)圖
* {@link ListPrimAndKruskal#prim()} Prim算法實現(xiàn)最小生成樹
* {@link ListPrimAndKruskal#kruskal()} Kruskal算法實現(xiàn)最小生成樹
* {@link ListPrimAndKruskal#getEdges()} 獲取邊集數(shù)組
*
* @author lx
* @date 2020/5/14 23:31
*/
public class ListPrimAndKruskal<E> {
/**
* 頂點類
*
* @param <E>
*/
private class Node<E> {
/**
* 頂點信息
*/
E data;
/**
* 指向第一條依附該頂點的邊
*/
LNode firstLNode;
public Node(E data, LNode firstLNode) {
this.data = data;
this.firstLNode = firstLNode;
}
}
/**
* 邊表節(jié)點類
*/
private class LNode {
/**
* 該邊所指向的頂點的索引位置
*/
int vertex;
/**
* 該邊的權(quán)值
*/
int weight;
/**
* 指向下一條邊的指針
*/
LNode nextLNode;
}
/**
* 邊對象,具有權(quán)值,在構(gòu)建加權(quán)無向圖時使用
*/
private static class Edge<E> {
private E from;
private E to;
private int weight;
public Edge(E from, E to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
@Override
public String toString() {
return "Edge{" +
"from=" + from +
", to=" + to +
", weight=" + weight +
'}';
}
}
/**
* 頂點數(shù)組
*/
private Node<E>[] vertexs;
/**
* 邊數(shù)組
*/
private Edge<E>[] edges;
/**
* 由于是加權(quán)圖,這里設(shè)置一個邊的權(quán)值上限,任何邊的最大權(quán)值不能大于等于該值，在實際應(yīng)用中，該值應(yīng)該根據(jù)實際情況確定
*/
private static final int NO_EDGE = 99;
/**
* 創(chuàng)建無向加權(quán)圖
*
* @param vexs 頂點數(shù)組
* @param edges 邊二維數(shù)組
*/
public ListPrimAndKruskal(E[] vexs, Edge<E>[] edges) {
this.edges = edges;
/*初始化頂點數(shù)組,并添加頂點*/
vertexs = new Node[vexs.length];
for (int i = 0; i < vertexs.length; i++) {
vertexs[i] = new Node<>(vexs[i], null);
}
/*初始化邊表,并添加邊節(jié)點到邊表尾部,即采用尾插法*/
for (Edge<E> edge : edges) {
// 讀取一條邊的起始頂點和結(jié)束頂點索引值
int p1 = getPosition(edge.from);
int p2 = getPosition(edge.to);
int weight = edge.weight;
/*這里需要相互添加邊節(jié)點,無向圖可以看作相互可達的有向圖*/
// 初始化lnode1邊節(jié)點
LNode lnode1 = new LNode();
lnode1.vertex = p2;
lnode1.weight = weight;
// 將LNode鏈接到"p1所在鏈表的末尾"
if (vertexs[p1].firstLNode == null) {
vertexs[p1].firstLNode = lnode1;
} else {
linkLast(vertexs[p1].firstLNode, lnode1);
}
// 初始化lnode2邊節(jié)點
LNode lnode2 = new LNode();
lnode2.vertex = p1;
lnode2.weight = weight;
// 將lnode2鏈接到"p2所在鏈表的末尾"
if (vertexs[p2].firstLNode == null) {
vertexs[p2].firstLNode = lnode2;
} else {
linkLast(vertexs[p2].firstLNode, lnode2);
}
}
}
/**
* 獲取某條邊的某個頂點所在頂點數(shù)組的索引位置
*
* @param e 頂點的值
* @return 所在頂點數(shù)組的索引位置, 或者-1 - 表示不存在
*/
private int getPosition(E e) {
for (int i = 0; i < vertexs.length; i++) {
if (vertexs[i].data == e) {
return i;
}
}
return -1;
}
/**
* 將lnode節(jié)點鏈接到邊表的最后,采用尾插法
*
* @param first 邊表頭結(jié)點
* @param node 將要添加的節(jié)點
*/
private void linkLast(LNode first, LNode node) {
while (true) {
if (first.vertex == node.vertex) {
return;
}
if (first.nextLNode == null) {
break;
}
first = first.nextLNode;
}
first.nextLNode = node;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < vertexs.length; i++) {
stringBuilder.append(i).append("(").append(vertexs[i].data).append("): ");
LNode node = vertexs[i].firstLNode;
while (node != null) {
stringBuilder.append(node.vertex).append("(").append(vertexs[node.vertex].data).append("-").append(node.weight).append(")");
node = node.nextLNode;
if (node != null) {
stringBuilder.append("->");
} else {
break;
}
}
stringBuilder.append("\n");
}
return stringBuilder.toString();
}
/**
* 深度優(yōu)先搜索遍歷圖的遞歸實現(xiàn),類似于樹的先序遍歷
* 因此模仿樹的先序遍歷,同樣借用棧結(jié)構(gòu),這里使用的是方法的遞歸,隱式的借用棧
*
* @param i 頂點索引
* @param visited 訪問標志數(shù)組
*/
private void DFS(int i, boolean[] visited) {
//索引索引標記為true ,表示已經(jīng)訪問了
visited[i] = true;
System.out.print(vertexs[i].data + " ");
//獲取該頂點的邊表頭結(jié)點
LNode node = vertexs[i].firstLNode;
//循環(huán)遍歷該頂點的鄰接點,采用同樣的方式遞歸搜索
while (node != null) {
if (!visited[node.vertex]) {
DFS(node.vertex, visited);
}
node = node.nextLNode;
}
}
/**
* 深度優(yōu)先搜索遍歷圖,類似于樹的前序遍歷,
*/
public void DFS() {
//新建頂點訪問標記數(shù)組,對應(yīng)每個索引對應(yīng)相同索引的頂點數(shù)組中的頂點
boolean[] visited = new boolean[vertexs.length];
//初始化所有頂點都沒有被訪問
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("DFS: ");
/*循環(huán)搜索*/
for (int i = 0; i < vertexs.length; i++) {
//如果對應(yīng)索引的頂點的訪問標記為false,則搜索該頂點
if (!visited[i]) {
DFS(i, visited);
}
}
/*走到這一步,說明頂點訪問標記數(shù)組全部為true,說明全部都訪問到了,深度搜索結(jié)束*/
System.out.println();
}
/**
* 廣度優(yōu)先搜索圖,類似于樹的層序遍歷
* 因此模仿樹的層序遍歷,同樣借用隊列結(jié)構(gòu)
*/
public void BFS() {
// 輔組隊列
Queue<Integer> indexLinkedList = new LinkedList<>();
//新建頂點訪問標記數(shù)組,對應(yīng)每個索引對應(yīng)相同索引的頂點數(shù)組中的頂點
boolean[] visited = new boolean[vertexs.length];
//初始化所有頂點都沒有被訪問
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("BFS: ");
for (int i = 0; i < vertexs.length; i++) {
//如果訪問方劑為false,則設(shè)置為true,表示已經(jīng)訪問,然后開始訪問
if (!visited[i]) {
visited[i] = true;
System.out.print(vertexs[i].data + " ");
indexLinkedList.add(i);
}
//判斷隊列是否有值,有就開始遍歷
if (!indexLinkedList.isEmpty()) {
//出隊列
Integer j = indexLinkedList.poll();
LNode node = vertexs[j].firstLNode;
while (node != null) {
int k = node.vertex;
if (!visited[k]) {
visited[k] = true;
System.out.print(vertexs[k].data + " ");
//繼續(xù)入隊列
indexLinkedList.add(k);
}
node = node.nextLNode;
}
}
}
System.out.println();
}
/**
* Prim算法求最小生成樹
*/
public void prim() {
System.out.println("prim: ");
//對應(yīng)節(jié)點應(yīng)該被連接的前驅(qū)節(jié)點,用來輸出
//默認為0,即前驅(qū)結(jié)點為第一個節(jié)點
int[] mid = new int[vertexs.length];
int start = 0;
int min, tmp, sum = 0;
int num = vertexs.length;
//頂點間邊的權(quán)值
//存儲未連接頂點到已連接頂點的最短距離(最小權(quán))
int[] dis = new int[num];
// 初始化"頂點的權(quán)值數(shù)組"，
// 將每個頂點的權(quán)值初始化為"第start個頂點"到"該頂點"的權(quán)值。
//首先將其他頂點到0索引頂點的權(quán)值存儲進去
for (int i = 0; i < num; i++) {
dis[i] = getWeight(start, i);
}
//如果某頂點作為末端頂點被連接，對應(yīng)位置應(yīng)該為true
//第一個頂點默認被連接
boolean[] connected = new boolean[vertexs.length];
connected[0] = true;
/*默認第一個頂點已經(jīng)找到了,因此最多還要需要大循環(huán)n-1次*/
for (int k = 1; k < num; k++) {
min = NO_EDGE;
//最小權(quán)值的頂點的索引
int minIndex = 0;
// 在未被加入到最小生成樹的頂點中，找出權(quán)值最小的頂點。
for (int i = 1; i < vertexs.length; i++) {
//排除已連接的頂點,排除權(quán)值等于0的值,因為這里默認頂點指向自己的權(quán)值為0
if (!connected[i] && dis[i] != 0 && dis[i] < min) {
min = dis[i];
minIndex = i;
}
}
//如果沒找到,那么該圖可能不是連通圖,直接返回了,此時最小生成樹沒啥意義
if (minIndex == 0) {
return;
}
//權(quán)值和增加
sum += min;
//該新連接頂點對應(yīng)的索引值變成true,表示已被連接,后續(xù)判斷時跳過該頂點
connected[minIndex] = true;
//輸出對應(yīng)的前驅(qū)頂點到該最小頂點的權(quán)值
System.out.println(vertexs[mid[minIndex]].data + " ---> " + vertexs[minIndex].data + " 權(quán)值:" + min);
/*在新頂點minIndex加入之前的其他所有頂點到連接頂點最小的權(quán)值已經(jīng)計算過了
因此只需要更新其他頂點到新連接頂點minIndex是否還有更短的權(quán)值,有的話就更新找到距離已連接的頂點權(quán)最小的頂點*/
for (int i = 1; i < num; i++) {
//如果該頂點未連接
if (!connected[i]) {
// 獲取minindex頂點到未連接頂點i的權(quán)值
tmp = getWeight(minIndex, i);
/*如果新頂點到未連接頂點i的權(quán)值不為0,并且比原始頂點到未連接頂點i的權(quán)值還要小,那么更新對應(yīng)位置的最小權(quán)值*/
if (tmp != 0 && dis[i] > tmp) {
dis[i] = tmp;
//更新前驅(qū)節(jié)點索引為新加入節(jié)點索引
mid[i] = minIndex;
}
}
}
}
System.out.println("sum: " + sum);
}
/**
* 嘗試獲取邊起點start到邊終點end的邊的權(quán)值,當然可能獲取不到
*
* @param start 邊起點
* @param end 邊終點
* @return 返回權(quán)值; 如果起點和終點相同則返回0;如果邊起點和邊終點之間并沒有邊, 則返回NO_EDGE
*/
private int getWeight(int start, int end) {
//如果start=end，則返回0
if (start == end) {
return 0;
}
//獲取該頂點的邊表的第一個值
LNode node = vertexs[start].firstLNode;
//循環(huán)查找邊表,看能否找到對應(yīng)的索引=end,找不到就返回NO_EDGE,表示兩個頂點未連接。
while (node != null) {
if (end == node.vertex) {
return node.weight;
}
node = node.nextLNode;
}
return NO_EDGE;
}
/**
* Kruskal算法求最小生成樹,可以說鄰接矩陣和鄰接鏈表的實現(xiàn)方式是完全一致的
*/
public void kruskal() {
//由于創(chuàng)建圖的時候保存了邊集數(shù)組,這里直接使用就行了
//Edge[] edges = getEdges();
//this.edges=edges;
//對邊集數(shù)組進行排序
Arrays.sort(this.edges, Comparator.comparingInt(o -> o.weight));
// 用于保存已有最小生成樹中每個頂點在該最小樹中的最終終點的索引
int[] vends = new int[this.edges.length];
//能夠知道終點索引范圍是[0,this.edges.length-1],因此填充edges.length表示沒有終點
Arrays.fill(vends, this.edges.length);
int sum = 0;
for (Edge<E> edge : this.edges) {
// 獲取第i條邊的起點索引from
int from = getPosition(edge.from);
// 獲取第i條邊的終點索引to
int to = getPosition(edge.to);
// 獲取頂點from在"已有的最小生成樹"中的終點
int m = getEndIndex(vends, from);
// 獲取頂點to在"已有的最小生成樹"中的終點
int n = getEndIndex(vends, to);
// 如果m!=n，意味著沒有形成環(huán)路,則可以添加,否則直接跳過,進行下一條邊的判斷
if (m != n) {
//添加設(shè)置原始終點索引m在已有的最小生成樹中的終點為n
vends[m] = n;
System.out.println(vertexs[from].data + " ---> " + vertexs[to].data + " 權(quán)值:" + edge.weight);
sum += edge.weight;
}
}
System.out.println("sum: " + sum);
//System.out.println(Arrays.toString(this.edges));
}
/**
* 獲取頂點索引i的終點如果沒有終點則返回頂點索引本身
*
* @param vends 頂點在最小生成樹中的終點
* @param i 頂點索引
* @return 頂點索引i的終點如果沒有終點則返回頂點索引本身
*/
private int getEndIndex(int[] vends, int i) {
//這里使用循環(huán)查找的邏輯,尋找的是最終的終點
while (vends[i] != this.edges.length) {
i = vends[i];
}
return i;
}
/**
* 如果沒有現(xiàn)成的邊集數(shù)組，那么根據(jù)鄰接表結(jié)構(gòu)獲取圖中的邊集數(shù)組
*
* @return 圖的邊集數(shù)組
*/
private Edge[] getEdges() {
List<Edge> edges = new ArrayList<>();
//遍歷頂點數(shù)組
for (int i = 0; i < vertexs.length; i++) {
LNode node = vertexs[i].firstLNode;
while (node != null) {
//只需添加起點索引小于終點索引的邊就行了
if (node.vertex > i) {
edges.add(new Edge<>(vertexs[i].data, vertexs[node.vertex].data, node.weight));
}
node = node.nextLNode;
}
}
return edges.toArray(new Edge[0]);
}
public static void main(String[] args) {
//頂點數(shù)組
Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
//邊數(shù)組,加權(quán)值
Edge[] edges = {
new Edge('A', 'C', 1),
new Edge('D', 'A', 2),
new Edge('A', 'F', 3),
new Edge('B', 'C', 4),
new Edge('C', 'D', 5),
new Edge('E', 'G', 6),
new Edge('E', 'B', 7),
new Edge('D', 'B', 8),
new Edge('F', 'G', 9)};
//構(gòu)建圖
ListPrimAndKruskal<Character> listPrimAndKruskal = new ListPrimAndKruskal<Character>(vexs, edges);
//輸出圖
System.out.println(listPrimAndKruskal);
//深度優(yōu)先遍歷
//DFS:
//A C B E G F D
listPrimAndKruskal.DFS();
//廣度優(yōu)先遍歷
//BFS:
//A C D F B G E
listPrimAndKruskal.BFS();
//Prim算法求最小生成樹
listPrimAndKruskal.prim();
//Kruskal算法求最小生成樹
listPrimAndKruskal.kruskal();
//獲取邊集數(shù)組
Edge[] edges1 = listPrimAndKruskal.getEdges();
System.out.println(Arrays.toString(edges1));
}
}6 總結(jié)
最小生成樹能夠有效的解決生活中的最小經(jīng)費問題，但是有一部分問題卻不能解決，比如求兩個不直接相通的站點之間的最短通行時間問題，這里求的就不是最小生成樹了，因為不需要連通所有站點，而是只需要最短通行時間路徑，即最短路徑。
以上就是Java求最小生成樹的兩種算法詳解的詳細內(nèi)容，更多關(guān)于Java最小生成樹的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
詳解SpringMVC的url-pattern配置及原理剖析
這篇文章主要介紹了SpringMVC的url-pattern配置及原理剖析，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-06-06
Java讀取項目json文件并轉(zhuǎn)為JSON對象的操作
這篇文章主要介紹了Java讀取項目json文件并轉(zhuǎn)為JSON對象的操作，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-08-08
Nacos?是阿里巴巴推出來的一個新開源項目，這是一個更易于構(gòu)建云原生應(yīng)用的動態(tài)服務(wù)發(fā)現(xiàn)、配置管理和服務(wù)管理平臺，Nacos?幫助您更敏捷和容易地構(gòu)建、交付和管理微服務(wù)平臺，對Nacos相關(guān)基本知識感興趣的朋友一起看看吧2023-08-08
Mybatis Generator可以幫助我們自動生成很多結(jié)構(gòu)化的代碼，比如每張表對應(yīng)的Entity、Mapper接口和Xml文件，可以省去很多繁瑣的工作，今天通過本文給大家介紹Mybatis Generator的具體使用教程，感興趣的朋友一起看看吧2022-02-02
如何利用Java?AWT?創(chuàng)建一個簡易計算器
這篇文章主要介紹了如何利用Java?AWT?創(chuàng)建一個簡易計算器，AWT?是一個有助于構(gòu)建?GUI?的?API?基于?java?應(yīng)用程序，下面關(guān)于其相關(guān)資料實現(xiàn)計算器的內(nèi)容詳細,需要的朋友可以參考一下2022-03-03
SpringBoot集成WebSocket實現(xiàn)后臺向前端推送信息的示例
這篇文章主要介紹了SpringBoot集成WebSocket實現(xiàn)后臺向前端推送信息的示例，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-12-12
這篇文章主要介紹了基于Feign傳輸對象無法接收參數(shù)的問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-03-03
本文介紹了Java動態(tài)腳本Groovy，Groovy是用于Java虛擬機的一種敏捷的動態(tài)語言，它是一種成熟的面向?qū)ο缶幊陶Z言，既可以用于面向?qū)ο缶幊蹋挚梢杂米骷兇獾哪_本語言。使用該種語言不必編寫過多的代碼，同時又具有閉包和動態(tài)語言中的其他特性,需要的朋友可以參考一下2021-12-12
這篇文章主要給大家介紹了關(guān)于Java計算時間差和日期差五種常用示例的相關(guān)資料,最近工作中遇到需要計算時間差和日期差,搜索了幾種計算時間差和日期差的方法,這里總結(jié)一下,需要的朋友可以參考下2023-08-08
這篇文章主要介紹了使用java實現(xiàn)的京東商城登陸示例,需要的朋友可以參考下2014-03-03