所谓有权图,就是图中的每一条边上都会有相应的一个或一组值。通常情况下,这个值只是一个数字
如:在交通运输网中,边上的权值可能表示的是路程,也可能表示的是运输费用(显然二者都是数字)。不过,边上的权值也有可能是其它东西,比如说是一个字符串,甚至是一个更加复杂的数据包,里面集合了更多的数据
克鲁斯卡尔算法的核心思想是:在带权连通图中,不断地在边集合中找到最小的边,如果该边满足得到最小生成树的条件,就将其构造,直到最后得到一颗最小生成树。
克鲁斯卡尔算法的执行步骤:
第一步:在带权连通图中,将边的权值排序;
第二步:判断是否需要选择这条边(此时图中的边已按权值从小到大排好序)。判断的依据是边的两个顶点是否已连通,如果连通则继续下一条;如果不连通,那么就选择使其连通。
第三步:循环第二步,直到图中所有的顶点都在同一个连通分量中,即得到最小生成树。
关于有权图的实现,看如下实例:
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