所謂有權圖，就是圖中的每一條邊上都會有相應的一個或一組值。通常情況下，這個值只是一個數字
如：在交通運輸網中，邊上的權值可能表示的是路程，也可能表示的是運輸費用（顯然二者都是數字）。不過，邊上的權值也有可能是其它東西，比如說是一個字符串，甚至是一個更加復雜的數據包，里面集合了更多的數據
克魯斯卡爾算法的核心思想是：在帶權連通圖中，不斷地在邊集合中找到最小的邊，如果該邊滿足得到最小生成樹的條件，就將其構造，直到最后得到一顆最小生成樹。
克魯斯卡爾算法的執行步驟：
第一步：在帶權連通圖中，將邊的權值排序；
第二步：判斷是否需要選擇這條邊（此時圖中的邊已按權值從小到大排好序）。判斷的依據是邊的兩個頂點是否已連通，如果連通則繼續下一條；如果不連通，那么就選擇使其連通。
第三步：循環第二步，直到圖中所有的頂點都在同一個連通分量中，即得到最小生成樹。
關于有權圖的實現，看如下實例：
graph:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
package kruskal;public class graph { final int max=100; /* * 頂點節點 */ public class vexnode{ int adjvex; int data; } vexnode[] vexnodes; int[] thevexs; //頂點集合 int[][] edges = new int[max][max]; //邊集合 /* * 創建圖 */ public void creategraph(graph graph,int[][] a,int[] vexs) { thevexs=vexs; for (int i = 0; i < vexs.length; i++) { for (int j = 0; j < vexs.length; j++) { graph.edges[i][j] = a[i][j]; } } } /* * 輸出圖 */ public void printgraph(graph graph) { for (int i = 0; i < graph.thevexs.length; i++) { for (int j = 0; j < graph.thevexs.length; j++) { //沒有路徑則輸出/ if (graph.edges[i][j]==-1) { system.out.printf("%4s","/"); } else { system.out.printf("%4d",graph.edges[i][j]); } } system.out.println("\n"); } }} |
算法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
package kruskal;public class kruskal { public class edge{ int start; int end; int weight; } public void sortedge(edge[] e,int e) { edge temp; int j; for (int i = 0; i < e; i++) { temp=e[i]; j=i-1; while (j>=0&&temp.weight<e[j].weight) { e[j+1] = e[j]; j--; } e[j+1] = temp; } } public kruskal(graph graph) { int i,j,u1,v1,sn1,sn2,k; int[] vset = new int[100]; edge[] e = new edge[100]; k=0; for (i=0;i<graph.thevexs.length;i++) { for (j=0;j<=i;j++) { e[k] = new edge(); if (graph.edges[i][j]>0) { e[k].start=i; e[k].end=j; e[k].weight=graph.edges[i][j]; k++; } } } sortedge(e, k); for (i=0;i<graph.thevexs.length;i++) { vset[i]=i; } k=1; j=0; while (k<graph.thevexs.length) { u1=e[j].start; v1=e[j].end; sn1=vset[u1]; sn2=vset[v1]; if (sn1!=sn2) { system.out.printf("(%d,%d),權值：%d",u1,v1,e[j].weight); system.out.println("\n"); k++; for (i=0;i<graph.thevexs.length;i++) { if (vset[i]==sn2) { vset[i]=sn1; } } } j++; } }} |
測試類：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
package kruskal;public class test { public static void main(string[] args) { int[] vexs = {0,1,2,3,4}; int[][] a = { {0,1,3,4,7}, {1,0,2,-1,-1}, {3,2,0,5,8}, {4,-1,5,0,6}, {7,-1,8,6,0} }; graph graph = new graph(); graph.creategraph(graph, a, vexs); graph.printgraph(graph); kruskal kruskal = new kruskal(graph); }} |
總結
以上就是本文關于java語言基于無向有權圖實現克魯斯卡爾算法代碼示例的全部內容，希望對大家有所幫助。有什么問題可以隨時留言，小編盡力為您答復。
原文鏈接：http://blog.csdn.net/coder_py/article/details/72629260
