Java语言基于无向有权图实现克鲁斯卡尔算法代码示例

时间:2022-09-23 20:06:51

所谓有权图,就是图中的每一条边上都会有相应的一个或一组值。通常情况下,这个值只是一个数字

如:在交通运输网中,边上的权值可能表示的是路程,也可能表示的是运输费用(显然二者都是数字)。不过,边上的权值也有可能是其它东西,比如说是一个字符串,甚至是一个更加复杂的数据包,里面集合了更多的数据

克鲁斯卡尔算法的核心思想是:在带权连通图中,不断地在边集合中找到最小的边,如果该边满足得到最小生成树的条件,就将其构造,直到最后得到一颗最小生成树。

克鲁斯卡尔算法的执行步骤:

第一步:在带权连通图中,将边的权值排序;

第二步:判断是否需要选择这条边(此时图中的边已按权值从小到大排好序)。判断的依据是边的两个顶点是否已连通,如果连通则继续下一条;如果不连通,那么就选择使其连通。

第三步:循环第二步,直到图中所有的顶点都在同一个连通分量中,即得到最小生成树。

关于有权图的实现,看如下实例:

Java语言基于无向有权图实现克鲁斯卡尔算法代码示例

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