Java求最小生成樹的兩種算法詳解
更新時間：2022年01月25日 15:34:03 作者：劉Java
最小生成樹（Minimum Spanning Tree）：在連通圖的所有生成樹中，所有邊的權值和最小的生成樹，稱為最小生成樹。這篇文章主要介紹了求最小生成樹的兩種方法：Prim算法和Kruskal算法，需要的可以參考一下
介紹了圖的最小生成樹的概念，然后介紹了求最小生成樹的兩種算法：Prim算法和Kruskal算法的原理，最后提供了基于鄰接矩陣和鄰接鏈表的圖對兩種算法的Java實現(xiàn)。
閱讀本文需要一定的圖的基礎，如果對于圖不是太明白的可以看看這篇文章：Java數(shù)據(jù)結(jié)構(gòu)之圖的原理與實現(xiàn)。
1 最小生成樹的概述
生成樹（SpanningTree）：一個連通圖的生成樹是指一個連通子圖，它含有圖中全部n個頂點，但只有足以構(gòu)成一棵樹的n-1條邊。一顆有n個頂點的生成樹有且僅有n-1條邊，如果生成樹中再添加一條邊，則必定成環(huán)。
最小生成樹（Minimum Spanning Tree）：在連通圖的所有生成樹中，所有邊的權值和最小的生成樹，稱為最小生成樹。
在生活中，圖形結(jié)構(gòu)的應用是最廣泛的。比如常見的通信網(wǎng)絡搭建路線選擇，村莊可以看作頂點，村莊之間如果有通信路徑，則算作兩點之間的邊或者弧，兩個村莊之間的通信成本，可以看作邊或者弧的權值。
上圖就是生活中通信網(wǎng)絡搭建路線的選擇映射到圖形結(jié)構(gòu)的案例。頂點作為村莊，村莊之間如果有通信路徑則擁有邊，村莊的之間的通信搭建成本則是邊的權值。
一種很常見的需求是要求對于能夠通信的村莊都必須通信，并且通信建設成本和最小，畢竟經(jīng)費“有限”，省下來的經(jīng)費，嘿嘿！
上面的問題，轉(zhuǎn)換為數(shù)學模型，就是求一個圖的最小生成樹的問題，即：選出一條路線，連通了所有能夠連通頂點，并且權值和最小。這樣的問題已經(jīng)有了很多種解法，最經(jīng)典的有兩種算法，普里姆（Prim）算法和克魯斯卡爾（Kruskal)算法。
2 普里姆算法（Prim）
2.1 原理
普里姆（Prim）算法是以某頂點為起點，假設所有頂點均未連接，逐步找各頂點上最小權值的邊來連接并構(gòu)建最小生成樹。是以點為目標去構(gòu)建最小生成樹。
具體的步驟是： 首先隨機選取一個頂點a，尋找頂點a可連接所有的頂點，選擇一個權值低的頂點進行連接；然后尋找與這兩個頂點或可連接的所有頂點，選擇一個權值低的頂點與其中一個頂點進行連接；如此往復n-1次，每次選擇距離任意一個已連接末端頂點最短的頂點（而不是距離首個頂點最短的頂點）進行連接，直到所有的頂點都進行連接，至此最小生成樹構(gòu)建完畢。
2.2 案例分析
該案例對應著下面實現(xiàn)代碼中的案例。
在上面的圖中，首先選擇頂點A作為已連接點，尋找頂點A可連接所有的頂點C、D、F，選擇一個權值低的頂點進行連接，這里選擇A-C；
然后尋找與A或C可連接的所有頂點（排除已連接的點），找到B、D、F，一共有4條邊可選，A-D、A-F、C-B、C-D，選擇一個權值低的頂點與其中一個頂點進行連接，這里明顯選擇A-D連接；
然后尋找與A或C或D可連接的所有頂點（排除已連接的點），找到B、F，一共有3條邊可選，C-B、D-B、A-F，選擇一個權值低的頂點與其中一個頂點進行連接，這里明顯選擇A-F連接；
然后尋找與A或C或D或F可連接的所有頂點（排除已連接的點），找到B、G，一共有3條邊可選，C-B、D-B、F-G，選擇一個權值低的頂點與其中一個頂點進行連接，這里明顯選擇C-B連接；
然后尋找與A或C或D或F或B可連接的所有頂點（排除已連接的點），找到E、G，一共有2條邊可選，B-E、F-G，選擇一個權值低的頂點與其中一個頂點進行連接，這里明顯選擇B-E連接；
然后尋找與A或C或D或F或B或E可連接的所有頂點（排除已連接的點），找到G，一共有2條邊可選，E-G、F-G，選擇一個權值低的頂點與其中一個頂點進行連接，這里明顯選擇E-G連接；
所有的頂點連接完畢，此時最小生成樹已經(jīng)構(gòu)建好了，最小權值為23。
3 克魯斯卡爾算法（Kruskal）
3.1 原理
克魯斯卡爾算法（Kruskal）根據(jù)邊的權值以遞增的方式逐漸建立最小生成樹，是以邊為目標去構(gòu)建最小生成樹。
具體的步驟是： 將加權圖每個頂點都看做森林，然后將圖中每條鄰接邊的權值按照升序的方式進行排列，接著從排列好的鄰接邊表中抽取權值最小的邊，寫入該邊的起始頂點和結(jié)束頂點，連接頂點將森林構(gòu)成樹，然后讀取起始結(jié)束頂點的鄰接邊，優(yōu)先抽取權值小的鄰接邊，繼續(xù)連接頂點將森林構(gòu)成樹。添加鄰接邊的要求是加入到圖中的鄰接邊不構(gòu)成回路（環(huán)）。如此反復進行，直到已經(jīng)添加n-1條邊為止。至此最小生成樹構(gòu)建完畢。
3.2 案例分析
該案例對應著下面實現(xiàn)代碼中的案例，傳統(tǒng)Kruskal算法過程如下：
首先獲取邊集數(shù)組并按照權值重小到大進行排序，在代碼中的排序本人直接使用的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)，權值總和增加1，繼續(xù)；
循環(huán)取出第2條邊D-A，判斷與已經(jīng)找到的最小生成樹不會形成環(huán)，權值總和增加2，繼續(xù)；
循環(huán)取出第3條邊A-F，判斷與已經(jīng)找到的最小生成樹不會形成環(huán)，權值總和增加3，繼續(xù)；
循環(huán)取出第4條邊B-C，判斷與已經(jīng)找到的最小生成樹不會形成環(huán)，權值總和增加4，繼續(xù)；
循環(huán)取出第5條邊C-D，判斷與已經(jīng)找到的最小生成樹會形成環(huán)，該條邊丟棄，繼續(xù)；
循環(huán)取出第6條邊E-G，判斷與已經(jīng)找到的最小生成樹不會形成環(huán)，權值總和增加6，繼續(xù)；
循環(huán)取出第7條邊E-B，判斷與已經(jīng)找到的最小生成樹不會形成環(huá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)找到了，最小生成樹的權值總和為23。
上面步驟中，判斷是否形成環(huán)很關鍵，通常的做法是，對已經(jīng)找到的最小生成樹的頂點進行排序（從起點到終點)，然后每新添加一條邊，就使用新添加邊的起點和終點取最小二叉樹中尋找，排序后的終點，找到的終點一致，則說明最小生成樹加上這條邊就會形成環(huán)，否則說明不會，那么更新排序的終點。
4 鄰接矩陣加權圖實現(xiàn)
這里的實現(xiàn)能夠構(gòu)造一個基于鄰接矩陣實現(xiàn)無向加權圖的類，并且提供深度優(yōu)先遍歷和廣度優(yōu)先遍歷的方法，提供獲取邊集數(shù)組的方法，提供Prim和Kruskal兩種求最小生成樹的方法。
/**
* 無向加權圖鄰接矩陣實現(xiàn)
* {@link MatrixPrimAndKruskal#MatrixPrimAndKruskal(E[], Edge[])} 構(gòu)建無向加權圖
* {@link MatrixPrimAndKruskal#DFS()} 深度優(yōu)先遍歷無向加權圖
* {@link MatrixPrimAndKruskal#BFS()} 廣度優(yōu)先遍歷無向加權圖
* {@link MatrixPrimAndKruskal#toString()} 輸出無向加權圖
* {@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;
/**
* 由于是加權圖,這里設置一個邊的權值上限,任何邊的最大權值不能大于等于該值，在實際應用中，該值應該根據(jù)實際情況確定
*/
private static final int NO_EDGE = 99;
/**
* 邊對象,具有權值,在構(gòu)建加權無向圖時使用
*/
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)建無向加權圖
*
* @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);
// 初始化邊矩陣,并預先填充邊信息
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ù)組,對應每個索引對應相同索引的頂點數(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ù)遞歸遍歷領接點
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ù)組,對應每個索引對應相同索引的頂點數(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對應著邊二維矩陣的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對應著邊二維矩陣的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: ");
//對應節(jié)點應該被連接的前驅(qū)節(jié)點,用來輸出
//默認為0,即前驅(qū)結(jié)點為第一個節(jié)點
int[] mid = new int[matrix.length];
//如果某頂點作為末端頂點被連接，對應位置應該為true
//第一個頂點默認被連接
boolean[] connected = new boolean[matrix.length];
connected[0] = true;
//存儲未連接頂點到已連接頂點的最短距離(最小權)
int[] dis = new int[matrix.length];
//首先將矩陣第一行即其他頂點到0索引頂點的權值拷貝進去
System.arraycopy(matrix[0], 0, dis, 0, matrix.length);
//存儲路徑長度
int sum = 0;
//最小權值
int min;
/*默認第一個頂點已經(jīng)找到了,因此最多還要需要大循環(huán)n-1次*/
for (int k = 1; k < matrix.length; k++) {
min = NO_EDGE;
//最小權值的頂點的索引
int minIndex = 0;
/*尋找權值最小的且未被連接的頂點索引*/
for (int i = 1; i < matrix.length; i++) {
//排除已連接的頂點,排除權值等于0的值,這里權值等于0表示已生成的最小生成樹的頂點都未能與該頂點連接
if (!connected[i] && dis[i] != 0 && dis[i] < min) {
min = dis[i];
minIndex = i;
}
}
//如果沒找到,那么該圖可能不是連通圖,直接返回了,此時最小生成樹沒啥意義
if (minIndex == 0) {
return;
}
//權值和增加
sum += min;
//該新連接頂點對應的索引值變成true,表示已被連接,后續(xù)判斷時跳過該頂點
connected[minIndex] = true;
//輸出對應的前驅(qū)頂點到該最小頂點的權值
System.out.println(vertexs[mid[minIndex]] + " ---> " + vertexs[minIndex] + " 權值:" + min);
/*在新頂點minIndex加入之前的其他所有頂點到連接頂點最小的權值已經(jīng)計算過了
因此只需要更新其他未連接頂點到新連接頂點minIndex是否還有更短的權值,有的話就更新找到距離已連接的頂點權最小的頂點*/
for (int i = 1; i < matrix.length; i++) {
//如果該頂點未連接
if (!connected[i]) {
/*如果新頂點到未連接頂點i的權值不為0,并且比原始頂點到未連接頂點i的權值還要小,那么更新對應位置的最小權值*/
if (matrix[minIndex][i] != 0 && dis[i] > matrix[minIndex][i]) {
//更新最小權值
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) {
//添加設置原始終點索引m在已有的最小生成樹中的終點為n
vends[m] = n;
System.out.println(vertexs[from] + " ---> " + vertexs[to] + " 權值:" + 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ù)組
* 同樣是求最小權值的邊,但是有一個默認起點頂點,該起點可以是要求[0,頂點數(shù)量-1]之間的任意值，同時查找最小權的邊。
* 可能會有Bug,目前未發(fā)現(xiàn)
*/
public void kruskalAndPrim() {
System.out.println("kruskalAndPrim: ");
//已經(jīng)找到的邊攜帶的頂點對應的索引將變?yōu)閠rue,其余未找到邊對應的頂點將是false
boolean[] connected = new boolean[matrix.length];
//這里選擇第一個頂點為起點,表示以該頂點開始尋找包含該頂點的最小邊
connected[0] = true;
int sum = 0, n1 = 0, n2 = 0;
//最小權值
int min;
while (true) {
min = NO_EDGE;
/*找出所有帶有已找到頂點的邊中,最小權值的邊,只需要尋找對稱矩陣的一半即可*/
//第一維
for (int i = 0; i < matrix.length; i++) {
//第二維
for (int j = i + 1; j < matrix.length; j++) {
//排除等于0的,排除兩個頂點都找到了的,這里實際上已經(jīng)隱含了排除環(huán)的邏輯,如果某條邊的兩個頂點都找到了,那么如果算上該條邊,肯定會形成環(huán)
//尋找剩下的最小的權值的邊
if (matrix[i][j] != 0 && connected[i] != connected[j] && matrix[i][j] < min) {
min = matrix[i][j];
n1 = i;
n2 = j;
}
}
}
//如果沒找到最小權值,該圖可能不是連通圖,或者已經(jīng)尋找完畢,直接返回
if (min == NO_EDGE) {
System.out.println(" sum:" + sum);
return;
}
//已經(jīng)找到的邊對應的兩個頂點都置為true
connected[n1] = true;
connected[n2] = true;
//輸出找到的邊和最小權值
System.out.println(vertexs[n1] + " ---> " + vertexs[n2] + " 權值:" + min);
sum += min;
}
}
public static void main(String[] args) {
//頂點數(shù)組
Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
//邊數(shù)組,加權值
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 鄰接表加權圖實現(xiàn)
這里的實現(xiàn)能夠構(gòu)造一個基于鄰接表實現(xiàn)無向加權圖的類；并且提供深度優(yōu)先遍歷和廣度優(yōu)先遍歷的方法，提供獲取邊集數(shù)組的方法，提供Prim和Kruskal兩種求最小生成樹的方法。
/**
* 無向加權圖鄰接表實現(xiàn)
* {@link ListPrimAndKruskal#ListPrimAndKruskal(E[], Edge[])} 構(gòu)建無向加權圖
* {@link ListPrimAndKruskal#DFS()} 深度優(yōu)先遍歷無向加權圖
* {@link ListPrimAndKruskal#BFS()} 廣度優(yōu)先遍歷無向加權圖
* {@link ListPrimAndKruskal#toString()} 輸出無向加權圖
* {@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;
/**
* 該邊的權值
*/
int weight;
/**
* 指向下一條邊的指針
*/
LNode nextLNode;
}
/**
* 邊對象,具有權值,在構(gòu)建加權無向圖時使用
*/
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;
/**
* 由于是加權圖,這里設置一個邊的權值上限,任何邊的最大權值不能大于等于該值，在實際應用中，該值應該根據(jù)實際情況確定
*/
private static final int NO_EDGE = 99;
/**
* 創(chuàng)建無向加權圖
*
* @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ù)組,對應每個索引對應相同索引的頂點數(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++) {
//如果對應索引的頂點的訪問標記為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ù)組,對應每個索引對應相同索引的頂點數(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,則設置為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: ");
//對應節(jié)點應該被連接的前驅(qū)節(jié)點,用來輸出
//默認為0,即前驅(qū)結(jié)點為第一個節(jié)點
int[] mid = new int[vertexs.length];
int start = 0;
int min, tmp, sum = 0;
int num = vertexs.length;
//頂點間邊的權值
//存儲未連接頂點到已連接頂點的最短距離(最小權)
int[] dis = new int[num];
// 初始化"頂點的權值數(shù)組"，
// 將每個頂點的權值初始化為"第start個頂點"到"該頂點"的權值。
//首先將其他頂點到0索引頂點的權值存儲進去
for (int i = 0; i < num; i++) {
dis[i] = getWeight(start, i);
}
//如果某頂點作為末端頂點被連接，對應位置應該為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;
//最小權值的頂點的索引
int minIndex = 0;
// 在未被加入到最小生成樹的頂點中，找出權值最小的頂點。
for (int i = 1; i < vertexs.length; i++) {
//排除已連接的頂點,排除權值等于0的值,因為這里默認頂點指向自己的權值為0
if (!connected[i] && dis[i] != 0 && dis[i] < min) {
min = dis[i];
minIndex = i;
}
}
//如果沒找到,那么該圖可能不是連通圖,直接返回了,此時最小生成樹沒啥意義
if (minIndex == 0) {
return;
}
//權值和增加
sum += min;
//該新連接頂點對應的索引值變成true,表示已被連接,后續(xù)判斷時跳過該頂點
connected[minIndex] = true;
//輸出對應的前驅(qū)頂點到該最小頂點的權值
System.out.println(vertexs[mid[minIndex]].data + " ---> " + vertexs[minIndex].data + " 權值:" + min);
/*在新頂點minIndex加入之前的其他所有頂點到連接頂點最小的權值已經(jīng)計算過了
因此只需要更新其他頂點到新連接頂點minIndex是否還有更短的權值,有的話就更新找到距離已連接的頂點權最小的頂點*/
for (int i = 1; i < num; i++) {
//如果該頂點未連接
if (!connected[i]) {
// 獲取minindex頂點到未連接頂點i的權值
tmp = getWeight(minIndex, i);
/*如果新頂點到未連接頂點i的權值不為0,并且比原始頂點到未連接頂點i的權值還要小,那么更新對應位置的最小權值*/
if (tmp != 0 && dis[i] > tmp) {
dis[i] = tmp;
//更新前驅(qū)節(jié)點索引為新加入節(jié)點索引
mid[i] = minIndex;
}
}
}
}
System.out.println("sum: " + sum);
}
/**
* 嘗試獲取邊起點start到邊終點end的邊的權值,當然可能獲取不到
*
* @param start 邊起點
* @param end 邊終點
* @return 返回權值; 如果起點和終點相同則返回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)查找邊表,看能否找到對應的索引=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) {
//添加設置原始終點索引m在已有的最小生成樹中的終點為n
vends[m] = n;
System.out.println(vertexs[from].data + " ---> " + vertexs[to].data + " 權值:" + 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ù)組,加權值
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)容，更多關于Java最小生成樹的資料請關注腳本之家其它相關文章！
相關文章
正則表達式，又稱正規(guī)表示法、常規(guī)表示法（英語：Regular Expression，在代碼中常簡寫為regex、regexp或RE），計算機科學的一個概念2017-05-05
JMM要求保證可見性、原子性、有序性，volatile可以保證其中的兩個，本篇文章具體驗證volatile的可見性，不原子性和禁重排，同時解決volatile的不保證原子性，讓代碼具有原子性2022-12-12
這篇文章主要介紹了Java數(shù)組基礎詳解，具有一定參考價值，需要的朋友可以了解下。2017-11-11
這篇文章主要介紹了Java利用Optional解決空指針異常，Optional?類是一個包含有可選值的包裝類，這意味著?Optional?類既可以含有對象也可以為空2022-09-09
idea中無法自動裝配未找到 ‘XXXXXXX‘ 類型的 Bean
本文主要介紹了idea中無法自動裝配未找到 ‘XXXXXXX‘ 類型的 Bean的原因及三種解決方法,具有一定的參考價值,感興趣的可以了解一下2024-03-03
這篇文章主要為大家介紹了多模塊項目使用枚舉配置spring-cache緩存的方案詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-05-05
這篇文章主要介紹了springboot文件虛擬路徑映射方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-08-08
Java享元設計模式優(yōu)化對象創(chuàng)建提高性能和效率
Java享元設計模式通過共享可重用的對象，減少了系統(tǒng)中對象的數(shù)量，優(yōu)化了對象的創(chuàng)建和管理，提高了性能和效率。它是一種經(jīng)典的設計模式，適用于需要處理大量相似對象的應用程序2023-04-04
java生成餅圖svg，代碼實現(xiàn)感覺有點復雜，個人認為不如用JFreeChart，這篇文章主要介紹java生成餅圖svg及JFreeChart生成svg圖表，有需要的小伙伴可以參考下2015-08-08
SpringBoot如何通過@Profile注解配置多環(huán)境
在Spring中，可以使用配置文件的方式來指定不同環(huán)境下所需要的配置信息，本文給大家介紹SpringBoot如何通過@Profile注解配置多環(huán)境，感興趣的朋友跟隨小編一起看看吧2023-06-06