【数据结构】最小生成树之克鲁斯卡尔算法

我就是我 2022-10-02 12:52 139阅读 0赞

## 基本概念 ##

假设要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，自然会考虑如何在最省经费的前提下完成任务。

在一个**连通网**的所有生成树中，各边的代价之和最小的那棵生成树称为该连通网的**最小生成树**。

**MST性质**：最小生成树中必定存在一条具有最小权值的边。**普利姆(Prim)算法**和**克鲁斯卡尔(Kruskal)算法**是两个利用MST性质构成最小生成树的算法。

普利姆算法的核心思想是归并点，时间复杂度为O(n²)，适用于稠密网；

克鲁斯卡尔算法的核心思想是归并边，时间复杂度为O(elog2e)，使用与稀疏网。

## 克鲁斯卡尔算法（加边法） ##

如果说普利姆算法是“加点法”，那么克鲁斯卡尔算法就是“加边法”。

**<逻辑思路>**

（1）将由n个顶点组成的连通图拆分成n个连通分量，即每个顶点为一个连通分量；

（2）将图上的所有边按权值排序；

（3）从最小边开始操作，**归并边**的**判断条件**是下一条被选边不能使连通分量形成回路，即**被选边的两个顶点head和tail不能在同一个连通分量上**；

（4）在循环中执行某段代码，直至所有顶点被归并到同一连通分量。

**<实现思路>——以邻接矩阵为存储结构的无向网**

（1）按权值排序可以使用**“冒泡法”**和**“选择法”**；

（2）从步骤(3)可以看出，我们需要类似于普利姆算法中的closedge\[\]那样的**辅助数组**。包含的信息：每一条边的头顶点和尾顶点以及边上的权值；

（3）同时，我们还需要一个标记数组辅助判断**每一个顶点所属的连通分量**；

（4）归并一个顶点后，将顶点的连通分量改为并入它的连通分量。

typedef struct                         /*结构体数组的各元素代表各边*/
    {
        Vextype head;
        Vextype tail;
        Arctype lowcast;
    } Arcs[arcnum];
    
    int VexSet[vexnum];                    /*VexSet[vi-1] = i;表示vi所在的连通分量编号为i，即它本身*/
    
    void MiniSpanTree_Kruskal(AMGraph G)
    {
        for(int t = 0; t < arcnum; t++)    /*输入各边信息*/
            cin>>Arcs[t].head>>Arcs[t].tail>>Arcs[t].lowcast;
    
        Sort(Arcs);                        /*按权值将图上各边从小到大排序*/
    
        for(int t = 0; t < arcnum; t++)    /*对图上所有边（权值从小到大）依次进行操作*/
        {
            Headv = LocateVex(G, Arcs[t].head);        /*确定头尾顶点的编号*/
            Tailv = LocateVex(G, Arcs[t].tail);
            
            VS_h = VexSet[HeadV];                      /*确定头尾顶点所在的连通分量*/
            VS_t = VexSet[Tailv];
    
            if(VS_h != VS_t)                           /*若两个顶点不在同一连通分量*/
            {
                cout<<Arcs[t].head<<Arcs[t].tail;      /*输出符合要求的边*/
    
                for(int v = 0; v < G.vexnum; v++)      /*对所有顶点进行判断*/
                    if(VexSet[v] == VS_t)
                        VexSet[v] = VS_H;              /*将顶点归并到同一连通分量*/
            }
        }
    }