所謂有權(quán)圖，就是圖中的每一條邊上都會有相應(yīng)的一個或一組值。通常情況下，這個值只是一個數(shù)字

如：在交通運輸網(wǎng)中，邊上的權(quán)值可能表示的是路程，也可能表示的是運輸費用(顯然二者都是數(shù)字)。不過，邊上的權(quán)值也有可能是其它東西，比如說是一個字符串，甚至是一個更加復(fù)雜的數(shù)據(jù)包，里面集合了更多的數(shù)據(jù)

克魯斯卡爾算法的核心思想是：在帶權(quán)連通圖中，不斷地在邊集合中找到最小的邊，如果該邊滿足得到最小生成樹的條件，就將其構(gòu)造，直到最后得到一顆最小生成樹。

克魯斯卡爾算法的執(zhí)行步驟：

第一步：在帶權(quán)連通圖中，將邊的權(quán)值排序；

第二步：判斷是否需要選擇這條邊(此時圖中的邊已按權(quán)值從小到大排好序)。判斷的依據(jù)是邊的兩個頂點是否已連通，如果連通則繼續(xù)下一條；如果不連通，那么就選擇使其連通。

第三步：循環(huán)第二步，直到圖中所有的頂點都在同一個連通分量中，即得到最小生成樹。

關(guān)于有權(quán)圖的實現(xiàn)，看如下實例：

Graph:

package kruskal;

public class Graph {

final int max=100;

/*

* 頂點節(jié)點

*/

public class VexNode{

int adjvex;

int data;

}

VexNode[] vexNodes;

int[] thevexs;

//頂點集合

int[][] edges = new int[max][max];

//邊集合

/*

* 創(chuàng)建圖

*/

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+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

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

vset[i]=i;

}

k=1;

j=0;

while (k

u1=E[j].start;

v1=E[j].end;

sn1=vset[u1];

sn2=vset[v1];

if (sn1!=sn2) {

System.out.printf("(%d,%d),權(quán)值：%d",u1,v1,E[j].weight);

System.out.println("\n");

k++;

for (i=0;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);

}

}

總結(jié)

以上就是本文關(guān)于Java語言基于無向有權(quán)圖實現(xiàn)克魯斯卡爾算法代碼示例的全部內(nèi)容，希望對大家有所幫助。有什么問題可以隨時留言，小編盡力為您答復(fù)。

總結(jié)

以上是生活随笔為你收集整理的java克鲁斯卡尔算法_Java语言基于无向有权图实现克鲁斯卡尔算法代码示例的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。