所謂有權圖，就是圖中的每一條邊上都會有相應的一個或一組值。通常情況下，這個值只是一個數字
如：在交通運輸網中，邊上的權值可能表示的是路程，也可能表示的是運輸費用（顯然二者都是數字）。不過，邊上的權值也有可能是其它東西，比如說是一個字符串，甚至是一個更加複雜的數據包，裡面集合了更多的數據
克魯斯卡爾算法的核心思想是：在帶權連通圖中，不斷地在邊集合中找到最小的邊，如果該邊滿足得到最小生成樹的條件，就將其構造，直到最後得到一顆最小生成樹。
克魯斯卡爾算法的執行步驟：
第一步：在帶權連通圖中，將邊的權值排序；
第二步：判斷是否需要選擇這條邊（此時圖中的邊已按權值從小到大排好序）。判斷的依據是邊的兩個頂點是否已連通，如果連通則繼續下一條；如果不連通，那麼就選擇使其連通。
第三步：循環第二步，直到圖中所有的頂點都在同一個連通分量中，即得到最小生成樹。
關於有權圖的實現，看如下實例：
Graph:
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");}}}演算法:
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++;}}}測試類：
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語言基於無向有權圖實現克魯斯卡爾算法代碼示例的全部內容，希望對大家有所幫助。有什麼問題可以隨時留言，小編盡力為您答复。