算法研究：图解最小生成树之克鲁斯卡尔算法

我们在前面讲过的《克里姆算法》是以某个顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树的。同样的思 路，我们也可以直接就以边为目标去构建，因为权值为边上，直接找最小权值的边来构建生成树也是很自然的想法，只不过 构建时要考虑是否会形成环而已，此时我们就用到了图的存储结构中的边集数组结构，如图7-6-7

假设现在我们已经通 过邻接矩阵得到了边集数组edges并按权值从小到大排列如上图。

下面我们对着程序和每一步循环的图示来看：

算法代码：

typedef struct
{
    int begin;
    int end;
    int weight;
} Edge;

/* 查找连线顶点的尾部下标 */
int Find(int *parent, int f)
{
    while (parent[f] > 0)
        f = parent[f];

    return f;
}
/* 生成最小生成树 */
void MiniSpanTree_Kruskal(MGraph G)
{
    int i, j, n , m;
    int k = 0;
    int parent[MAXVEX];/* 定义一数组用来判断边与边是否形成环路 */

    Edge edges[MAXEDGE];/* 定义边集数组,edge的结构为begin,end,weight,均为整型 */

    /* 此处省略将邻接矩阵G转换为边集数组edges并按权由小到大排列的代码*/
    for (i = 0; i < G.numVertexes; i++)
        parent[i] = 0;

    cout << "打印最小生成树：" << endl;
    for (i = 0; i < G.numEdges; i++)/* 循环每一条边 */
    {
        n = Find(parent, edges[i].begin);
        m = Find(parent, edges[i].end);
        if (n != m)/* 假如n与m不等，说明此边没有与现有的生成树形成环路 */
        {
            parent[n] = m;/* 将此边的结尾顶点放入下标为起点的parent中。 */
            /* 表示此顶点已经在生成树集合中 */

            cout << "(" << edges[i].begin << ", " << edges[i].end << ") "
                 << edges[i].weight << endl;
        }
    }

}

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索算法
， 数组
， int
， 飞思卡尔、赛道中心线
， 克鲁斯卡尔算法
， 生成
， parent
， 最小
克鲁斯卡尔
，以便于您获取更多的相关知识。