Java教程

Kruskal算法

本文主要是介绍Kruskal算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

全知识整理目录

数据结构整理的目录包括了许多的数据结构相关知识。


目录

概述

算法的过程 

算法代码


概述

Kruskal算法是什么?

Kruskal算法是求最小生成树的一种算法,也是一种朴素算法,这种算法就是,在所有的结点当中,每次选择未被连接的权值最小的边。

那么最小生成树又是什么呢?

连通的,最小权值的图,就称为最小生成树。

算法的过程 

Kruskal算法又称为加边法,就是把最短的边,一条条加起来生成的树。

算法代码

/*
 * 克鲁斯卡尔(Kruskal)最小生成树
 */
void kruskal(Graph G)
{
    int i,m,n,p1,p2;
    int length;
    int index = 0;          // rets数组的索引
    int vends[MAX]={0};     // 用于保存"已有最小生成树"中每个顶点在该最小树中的终点。
    EData rets[MAX];        // 结果数组,保存kruskal最小生成树的边
    EData *edges;           // 图对应的所有边

    // 获取"图中所有的边"
    edges = get_edges(G);
    // 将边按照"权"的大小进行排序(从小到大)
    sorted_edges(edges, G.edgnum);

    for (i=0; i<G.edgnum; i++)
    {
        p1 = get_position(G, edges[i].start);   // 获取第i条边的"起点"的序号
        p2 = get_position(G, edges[i].end);     // 获取第i条边的"终点"的序号

        m = get_end(vends, p1);                 // 获取p1在"已有的最小生成树"中的终点
        n = get_end(vends, p2);                 // 获取p2在"已有的最小生成树"中的终点
        // 如果m!=n,意味着"边i"与"已经添加到最小生成树中的顶点"没有形成环路
        if (m != n)
        {
            vends[m] = n;                       // 设置m在"已有的最小生成树"中的终点为n
            rets[index++] = edges[i];           // 保存结果
        }
    }
    free(edges);

    // 统计并打印"kruskal最小生成树"的信息
    length = 0;
    for (i = 0; i < index; i++)
        length += rets[i].weight;
    printf("Kruskal=%d: ", length);
    for (i = 0; i < index; i++)
        printf("(%c,%c) ", rets[i].start, rets[i].end);
    printf("\n");
}

参考

克鲁斯卡尔(Kruskal)C语言的实现

最小生成树的两种方法(Kruskal算法和Prim算法)

这篇关于Kruskal算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!