溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細講解有關Java如何求最小生成樹，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。
生成樹（SpanningTree）：一個連通圖的生成樹是指一個連通子圖，它含有圖中全部n個頂點，但只有足以構成一棵樹的n-1條邊。一顆有n個頂點的生成樹有且僅有n-1條邊，如果生成樹中再添加一條邊，則必定成環。
最小生成樹（Minimum Spanning Tree）：在連通圖的所有生成樹中，所有邊的權值和最小的生成樹，稱為最小生成樹。
在生活中，圖形結構的應用是最廣泛的。比如常見的通信網絡搭建路線選擇，村莊可以看作頂點，村莊之間如果有通信路徑，則算作兩點之間的邊或者弧，兩個村莊之間的通信成本，可以看作邊或者弧的權值。
上圖就是生活中通信網絡搭建路線的選擇映射到圖形結構的案例。頂點作為村莊，村莊之間如果有通信路徑則擁有邊，村莊的之間的通信搭建成本則是邊的權值。
一種很常見的需求是要求對于能夠通信的村莊都必須通信，并且通信建設成本和最小，畢竟經費“有限”，省下來的經費，嘿嘿！
上面的問題，轉換為數學模型，就是求一個圖的最小生成樹的問題，即：選出一條路線，連通了所有能夠連通頂點，并且權值和最小。這樣的問題已經有了很多種解法，最經典的有兩種算法，普里姆（Prim）算法和克魯斯卡爾（Kruskal)算法。
普里姆（Prim）算法是以某頂點為起點，假設所有頂點均未連接，逐步找各頂點上最小權值的邊來連接并構建最小生成樹。是以點為目標去構建最小生成樹。
具體的步驟是： 首先隨機選取一個頂點a，尋找頂點a可連接所有的頂點，選擇一個權值低的頂點進行連接；然后尋找與這兩個頂點或可連接的所有頂點，選擇一個權值低的頂點與其中一個頂點進行連接；如此往復n-1次，每次選擇距離任意一個已連接末端頂點最短的頂點（而不是距離首個頂點最短的頂點）進行連接，直到所有的頂點都進行連接，至此最小生成樹構建完畢。
該案例對應著下面實現代碼中的案例。
在上面的圖中，首先選擇頂點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連接；
所有的頂點連接完畢，此時最小生成樹已經構建好了，最小權值為23。
克魯斯卡爾算法（Kruskal）根據邊的權值以遞增的方式逐漸建立最小生成樹，是以邊為目標去構建最小生成樹。
具體的步驟是： 將加權圖每個頂點都看做森林，然后將圖中每條鄰接邊的權值按照升序的方式進行排列，接著從排列好的鄰接邊表中抽取權值最小的邊，寫入該邊的起始頂點和結束頂點，連接頂點將森林構成樹，然后讀取起始結束頂點的鄰接邊，優先抽取權值小的鄰接邊，繼續連接頂點將森林構成樹。添加鄰接邊的要求是加入到圖中的鄰接邊不構成回路（環）。如此反復進行，直到已經添加n-1條邊為止。至此最小生成樹構建完畢。
該案例對應著下面實現代碼中的案例，傳統Kruskal算法過程如下：
首先獲取邊集數組并按照權值重小到大進行排序，在代碼中的排序本人直接使用的sort排序，也可以自己實現堆排序，排序后結果如下：
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}
循環取出第1條邊A-C，判斷與已經找到的最小生成樹不會形成環，權值總和增加1，繼續；
循環取出第2條邊D-A，判斷與已經找到的最小生成樹不會形成環，權值總和增加2，繼續；
循環取出第3條邊A-F，判斷與已經找到的最小生成樹不會形成環，權值總和增加3，繼續；
循環取出第4條邊B-C，判斷與已經找到的最小生成樹不會形成環，權值總和增加4，繼續；
循環取出第5條邊C-D，判斷與已經找到的最小生成樹會形成環，該條邊丟棄，繼續；
循環取出第6條邊E-G，判斷與已經找到的最小生成樹不會形成環，權值總和增加6，繼續；
循環取出第7條邊E-B，判斷與已經找到的最小生成樹不會形成環，權值總和增加7，繼續；
循環取出第8條邊D-B，判斷與已經找到的最小生成樹會形成環，該條邊丟棄，繼續；
循環取出第9條邊F-G，判斷與已經找到的最小生成樹會形成環，該條邊丟棄，繼續；
此時循環結束，那么最小生成樹也已經找到了，最小生成樹的權值總和為23。
上面步驟中，判斷是否形成環很關鍵，通常的做法是，對已經找到的最小生成樹的頂點進行排序（從起點到終點)，然后每新添加一條邊，就使用新添加邊的起點和終點取最小二叉樹中尋找，排序后的終點，找到的終點一致，則說明最小生成樹加上這條邊就會形成環，否則說明不會，那么更新排序的終點。
這里的實現能夠構造一個基于鄰接矩陣實現無向加權圖的類，并且提供深度優先遍歷和廣度優先遍歷的方法，提供獲取邊集數組的方法，提供Prim和Kruskal兩種求最小生成樹的方法。
/**
* 無向加權圖鄰接矩陣實現
* {@link MatrixPrimAndKruskal#MatrixPrimAndKruskal(E[], Edge[])} 構建無向加權圖
* {@link MatrixPrimAndKruskal#DFS()} 深度優先遍歷無向加權圖
* {@link MatrixPrimAndKruskal#BFS()} 廣度優先遍歷無向加權圖
* {@link MatrixPrimAndKruskal#toString()} 輸出無向加權圖
* {@link MatrixPrimAndKruskal#prim()} Prim算法實現最小生成樹
* {@link MatrixPrimAndKruskal#kruskal()} Kruskal算法實現最小生成樹
* {@link MatrixPrimAndKruskal#kruskalAndPrim()} Kruskal算法結合Prim算法實現最小生成樹
* {@link MatrixPrimAndKruskal#getEdges()} 獲取邊集數組
*
* @author lx
* @date 2020/5/14 18:13
*/
public class MatrixPrimAndKruskal<E> {
/**
* 頂點數組
*/
private Object[] vertexs;
/**
* 鄰接矩陣
*/
private int[][] matrix;
/**
*
*/
private Edge<E>[] edges;
/**
* 由于是加權圖,這里設置一個邊的權值上限,任何邊的最大權值不能大于等于該值，在實際應用中，該值應該根據實際情況確定
*/
private static final int NO_EDGE = 99;
/**
* 邊對象,具有權值,在構建加權無向圖時使用
*/
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 +
'}';
}
}
/**
* 創建無向加權圖
*
* @param vertexs 頂點數組
* @param edges 邊對象數組
*/
public MatrixPrimAndKruskal(Object[] vertexs, Edge<E>[] edges) {
//初始化邊數組
this.edges = edges;
// 初始化頂點數組,并添加頂點
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) {
// 讀取一條邊的起始頂點和結束頂點索引值
int p1 = getPosition(edge.from);
int p2 = getPosition(edge.to);
//對稱的兩個點位都置為edge.weight,無向圖可以看作相互可達的有向圖
this.matrix[p1][p2] = edge.weight;
this.matrix[p2][p1] = edge.weight;
}
}
/**
* 獲取某條邊的某個頂點所在頂點數組的索引位置
*
* @param e 頂點的值
* @return 所在頂點數組的索引位置, 或者-1 - 表示不存在
*/
private int getPosition(E e) {
for (int i = 0; i < vertexs.length; i++) {
if (vertexs[i] == e) {
return i;
}
}
return -1;
}
/**
* 深度優先搜索遍歷圖,類似于樹的前序遍歷,
*/
public void DFS() {
//新建頂點訪問標記數組,對應每個索引對應相同索引的頂點數組中的頂點
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();
}
/**
* 深度優先搜索遍歷圖的遞歸實現,類似于樹的先序遍歷
* 因此模仿樹的先序遍歷,同樣借用棧結構,這里使用的是方法的遞歸,隱式的借用棧
*
* @param i 頂點索引
* @param visited 訪問標志數組
*/
private void DFS(int i, boolean[] visited) {
visited[i] = true;
System.out.print(vertexs[i] + " ");
// 遍歷該頂點的所有鄰接點。若該鄰接點是沒有訪問過，那么繼續遞歸遍歷領接點
for (int w = firstVertex(i); w >= 0; w = nextVertex(i, w)) {
if (!visited[w]) {
DFS(w, visited);
}
}
}
/**
* 廣度優先搜索圖,類似于樹的層序遍歷
* 因此模仿樹的層序遍歷,同樣借用隊列結構
*/
public void BFS() {
// 輔組隊列
Queue<Integer> indexLinkedList = new LinkedList<>();
//新建頂點訪問標記數組,對應每個索引對應相同索引的頂點數組中的頂點
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();
//繼續訪問j的鄰接點
for (int k = firstVertex(j); k >= 0; k = nextVertex(j, k)) {
if (!visited[k]) {
visited[k] = true;
System.out.print(vertexs[k] + " ");
//繼續入隊列
indexLinkedList.add(k);
}
}
}
}
System.out.println();
}
/**
* 返回頂點v的第一個鄰接頂點的索引，失敗則返回-1
*
* @param v 頂點v在數組中的索引
* @return 返回頂點v的第一個鄰接頂點的索引，失敗則返回-1
*/
private int firstVertex(int v) {
//如果索引超出范圍,則返回-1
if (v < 0 || v > (vertexs.length - 1)) {
return -1;
}
/*根據鄰接矩陣的規律:頂點索引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;
}
/*根據鄰接矩陣的規律:頂點索引v對應著邊二維矩陣的matrix[v][i]一行記錄
* 由于鄰接點w的索引已經獲取了,所以從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: ");
//對應節點應該被連接的前驅節點,用來輸出
//默認為0,即前驅結點為第一個節點
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;
/*默認第一個頂點已經找到了,因此最多還要需要大循環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,表示已被連接,后續判斷時跳過該頂點
connected[minIndex] = true;
//輸出對應的前驅頂點到該最小頂點的權值
System.out.println(vertexs[mid[minIndex]] + " ---> " + vertexs[minIndex] + " 權值:" + min);
/*在新頂點minIndex加入之前的其他所有頂點到連接頂點最小的權值已經計算過了
因此只需要更新其他未連接頂點到新連接頂點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];
//更新前驅節點索引為新加入節點索引
mid[i] = minIndex;
}
}
}
}
System.out.println("sum: " + sum);
}
/**
* Kruskal算法求最小生成樹傳統實現,要求知道邊集數組,和頂點數組
*/
public void kruskal() {
System.out.println("Kruskal: ");
//由于創建圖的時候保存了邊集數組,這里直接使用就行了
//Edge[] edges = getEdges();
//this.edges=edges;
//對邊集數組進行排序
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，意味著沒有形成環路,則可以添加,否則直接跳過,進行下一條邊的判斷
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) {
//這里使用循環查找的邏輯,尋找的是最終的終點
while (vends[i] != this.edges.length) {
i = vends[i];
}
return i;
}
/**
* 如果沒有現成的邊集數組，那么根據鄰接矩陣結構獲取圖中的邊集數組
*
* @return 圖的邊集數組
*/
private Edge[] getEdges() {
List<Edge> edges = new ArrayList<>();
/*遍歷矩陣數組 只需要遍歷一半就行了*/
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結合Prim算法.不需要知道邊集,只需要矩陣數組,和頂點數組
* 同樣是求最小權值的邊,但是有一個默認起點頂點,該起點可以是要求[0,頂點數量-1]之間的任意值，同時查找最小權的邊。
* 可能會有Bug,目前未發現
*/
public void kruskalAndPrim() {
System.out.println("kruskalAndPrim: ");
//已經找到的邊攜帶的頂點對應的索引將變為true,其余未找到邊對應的頂點將是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的,排除兩個頂點都找到了的,這里實際上已經隱含了排除環的邏輯,如果某條邊的兩個頂點都找到了,那么如果算上該條邊,肯定會形成環
//尋找剩下的最小的權值的邊
if (matrix[i][j] != 0 && connected[i] != connected[j] && matrix[i][j] < min) {
min = matrix[i][j];
n1 = i;
n2 = j;
}
}
}
//如果沒找到最小權值,該圖可能不是連通圖,或者已經尋找完畢,直接返回
if (min == NO_EDGE) {
System.out.println(" sum:" + sum);
return;
}
//已經找到的邊對應的兩個頂點都置為true
connected[n1] = true;
connected[n2] = true;
//輸出找到的邊和最小權值
System.out.println(vertexs[n1] + " ---> " + vertexs[n2] + " 權值:" + min);
sum += min;
}
}
public static void main(String[] args) {
//頂點數組
Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
//邊數組,加權值
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)};
//構建圖
MatrixPrimAndKruskal<Character> matrixPrimAndKruskal = new MatrixPrimAndKruskal<Character>(vexs, edges);
//輸出圖
System.out.println(matrixPrimAndKruskal);
//深度優先遍歷
matrixPrimAndKruskal.DFS();
//廣度優先遍歷
matrixPrimAndKruskal.BFS();
//Prim算法輸出最小生成樹
matrixPrimAndKruskal.prim();
//Kruskal算法輸出最小生成樹
matrixPrimAndKruskal.kruskal();
//Kruskal算法結合Prim算法輸出最小生成樹,可能會有Bug,目前未發現
matrixPrimAndKruskal.kruskalAndPrim();
//獲取邊集數組
Edge[] edges1 = matrixPrimAndKruskal.getEdges();
System.out.println(Arrays.toString(edges1));
}
}這里的實現能夠構造一個基于鄰接表實現無向加權圖的類；并且提供深度優先遍歷和廣度優先遍歷的方法，提供獲取邊集數組的方法，提供Prim和Kruskal兩種求最小生成樹的方法。
/**
* 無向加權圖鄰接表實現
* {@link ListPrimAndKruskal#ListPrimAndKruskal(E[], Edge[])} 構建無向加權圖
* {@link ListPrimAndKruskal#DFS()} 深度優先遍歷無向加權圖
* {@link ListPrimAndKruskal#BFS()} 廣度優先遍歷無向加權圖
* {@link ListPrimAndKruskal#toString()} 輸出無向加權圖
* {@link ListPrimAndKruskal#prim()} Prim算法實現最小生成樹
* {@link ListPrimAndKruskal#kruskal()} Kruskal算法實現最小生成樹
* {@link ListPrimAndKruskal#getEdges()} 獲取邊集數組
*
* @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;
}
}
/**
* 邊表節點類
*/
private class LNode {
/**
* 該邊所指向的頂點的索引位置
*/
int vertex;
/**
* 該邊的權值
*/
int weight;
/**
* 指向下一條邊的指針
*/
LNode nextLNode;
}
/**
* 邊對象,具有權值,在構建加權無向圖時使用
*/
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 +
'}';
}
}
/**
* 頂點數組
*/
private Node<E>[] vertexs;
/**
* 邊數組
*/
private Edge<E>[] edges;
/**
* 由于是加權圖,這里設置一個邊的權值上限,任何邊的最大權值不能大于等于該值，在實際應用中，該值應該根據實際情況確定
*/
private static final int NO_EDGE = 99;
/**
* 創建無向加權圖
*
* @param vexs 頂點數組
* @param edges 邊二維數組
*/
public ListPrimAndKruskal(E[] vexs, Edge<E>[] edges) {
this.edges = edges;
/*初始化頂點數組,并添加頂點*/
vertexs = new Node[vexs.length];
for (int i = 0; i < vertexs.length; i++) {
vertexs[i] = new Node<>(vexs[i], null);
}
/*初始化邊表,并添加邊節點到邊表尾部,即采用尾插法*/
for (Edge<E> edge : edges) {
// 讀取一條邊的起始頂點和結束頂點索引值
int p1 = getPosition(edge.from);
int p2 = getPosition(edge.to);
int weight = edge.weight;
/*這里需要相互添加邊節點,無向圖可以看作相互可達的有向圖*/
// 初始化lnode1邊節點
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邊節點
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);
}
}
}
/**
* 獲取某條邊的某個頂點所在頂點數組的索引位置
*
* @param e 頂點的值
* @return 所在頂點數組的索引位置, 或者-1 - 表示不存在
*/
private int getPosition(E e) {
for (int i = 0; i < vertexs.length; i++) {
if (vertexs[i].data == e) {
return i;
}
}
return -1;
}
/**
* 將lnode節點鏈接到邊表的最后,采用尾插法
*
* @param first 邊表頭結點
* @param node 將要添加的節點
*/
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();
}
/**
* 深度優先搜索遍歷圖的遞歸實現,類似于樹的先序遍歷
* 因此模仿樹的先序遍歷,同樣借用棧結構,這里使用的是方法的遞歸,隱式的借用棧
*
* @param i 頂點索引
* @param visited 訪問標志數組
*/
private void DFS(int i, boolean[] visited) {
//索引索引標記為true ,表示已經訪問了
visited[i] = true;
System.out.print(vertexs[i].data + " ");
//獲取該頂點的邊表頭結點
LNode node = vertexs[i].firstLNode;
//循環遍歷該頂點的鄰接點,采用同樣的方式遞歸搜索
while (node != null) {
if (!visited[node.vertex]) {
DFS(node.vertex, visited);
}
node = node.nextLNode;
}
}
/**
* 深度優先搜索遍歷圖,類似于樹的前序遍歷,
*/
public void DFS() {
//新建頂點訪問標記數組,對應每個索引對應相同索引的頂點數組中的頂點
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++) {
//如果對應索引的頂點的訪問標記為false,則搜索該頂點
if (!visited[i]) {
DFS(i, visited);
}
}
/*走到這一步,說明頂點訪問標記數組全部為true,說明全部都訪問到了,深度搜索結束*/
System.out.println();
}
/**
* 廣度優先搜索圖,類似于樹的層序遍歷
* 因此模仿樹的層序遍歷,同樣借用隊列結構
*/
public void BFS() {
// 輔組隊列
Queue<Integer> indexLinkedList = new LinkedList<>();
//新建頂點訪問標記數組,對應每個索引對應相同索引的頂點數組中的頂點
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,表示已經訪問,然后開始訪問
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 + " ");
//繼續入隊列
indexLinkedList.add(k);
}
node = node.nextLNode;
}
}
}
System.out.println();
}
/**
* Prim算法求最小生成樹
*/
public void prim() {
System.out.println("prim: ");
//對應節點應該被連接的前驅節點,用來輸出
//默認為0,即前驅結點為第一個節點
int[] mid = new int[vertexs.length];
int start = 0;
int min, tmp, sum = 0;
int num = vertexs.length;
//頂點間邊的權值
//存儲未連接頂點到已連接頂點的最短距離(最小權)
int[] dis = new int[num];
// 初始化"頂點的權值數組"，
// 將每個頂點的權值初始化為"第start個頂點"到"該頂點"的權值。
//首先將其他頂點到0索引頂點的權值存儲進去
for (int i = 0; i < num; i++) {
dis[i] = getWeight(start, i);
}
//如果某頂點作為末端頂點被連接，對應位置應該為true
//第一個頂點默認被連接
boolean[] connected = new boolean[vertexs.length];
connected[0] = true;
/*默認第一個頂點已經找到了,因此最多還要需要大循環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,表示已被連接,后續判斷時跳過該頂點
connected[minIndex] = true;
//輸出對應的前驅頂點到該最小頂點的權值
System.out.println(vertexs[mid[minIndex]].data + " ---> " + vertexs[minIndex].data + " 權值:" + min);
/*在新頂點minIndex加入之前的其他所有頂點到連接頂點最小的權值已經計算過了
因此只需要更新其他頂點到新連接頂點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;
//更新前驅節點索引為新加入節點索引
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;
//循環查找邊表,看能否找到對應的索引=end,找不到就返回NO_EDGE,表示兩個頂點未連接。
while (node != null) {
if (end == node.vertex) {
return node.weight;
}
node = node.nextLNode;
}
return NO_EDGE;
}
/**
* Kruskal算法求最小生成樹,可以說鄰接矩陣和鄰接鏈表的實現方式是完全一致的
*/
public void kruskal() {
//由于創建圖的時候保存了邊集數組,這里直接使用就行了
//Edge[] edges = getEdges();
//this.edges=edges;
//對邊集數組進行排序
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，意味著沒有形成環路,則可以添加,否則直接跳過,進行下一條邊的判斷
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) {
//這里使用循環查找的邏輯,尋找的是最終的終點
while (vends[i] != this.edges.length) {
i = vends[i];
}
return i;
}
/**
* 如果沒有現成的邊集數組，那么根據鄰接表結構獲取圖中的邊集數組
*
* @return 圖的邊集數組
*/
private Edge[] getEdges() {
List<Edge> edges = new ArrayList<>();
//遍歷頂點數組
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) {
//頂點數組
Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
//邊數組,加權值
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)};
//構建圖
ListPrimAndKruskal<Character> listPrimAndKruskal = new ListPrimAndKruskal<Character>(vexs, edges);
//輸出圖
System.out.println(listPrimAndKruskal);
//深度優先遍歷
//DFS:
//A C B E G F D
listPrimAndKruskal.DFS();
//廣度優先遍歷
//BFS:
//A C D F B G E
listPrimAndKruskal.BFS();
//Prim算法求最小生成樹
listPrimAndKruskal.prim();
//Kruskal算法求最小生成樹
listPrimAndKruskal.kruskal();
//獲取邊集數組
Edge[] edges1 = listPrimAndKruskal.getEdges();
System.out.println(Arrays.toString(edges1));
}
}關于“Java如何求最小生成樹”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
