数据结构最小生成树之Kruskal算法

Love The Way You Lie 2023-10-08 09:46 39阅读 0赞

### `Kruskal`算法 ###

克鲁斯卡尔(`Kruskal`)算法，是用来求加权连通图的最小生成树的算法

大话数据结构定义

> 假设 N=(V,\{ E\})N=(V,\{E\})。图中每个顶点自成一个连通分量。在`E`中选择代价最小的边，若该边依附的顶点落在`T`中不同的连通分量上，则将此边加入到`T`中，否则社区此边而选择下一条代价最小的边，以此类推，直至`T`中所有顶点都在同一连通分量上为止。

**基本思想**

按照权值从小到大的顺序选择`n - 1`条边，并保证这`n - 1`条边不构成回路

**具体做法**

首先构造一个只含`n`个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林不产生回路，直至森林变成过一棵树为止

### `Kruskal`算法图解 ###

![Graph\_prim\_G4][Graph_prim_G4]

以上图`G4`为例，使用克鲁斯卡尔算法进行演示实现最小生成树，用`parent`表示

![Graph\_prim\_G4\_kruskal\_details][Graph_prim_G4_kruskal_details]

**第零步**： 将邻接矩阵转换为边表数组，并且按权值大小排序

**第一步**： 将边<E,F><E,F>加入最小生成树中

边<E,F><E,F>的权值最小，故将其加入最小生成树

**第二步**： 将边<C,D><C,D>加入最小生成树中

上一步操作后， 边<C,D><C,D>的权值最小，故将其加入最小生成树

**第三步**： 将边<D,E><D,E>加入最小生成树中

上一步操作后， 边<D,E><D,E>的权值最小，故将其加入最小生成树

**第四步**： 将边<B,F><B,F>加入最小生成树中

上一步操作后，边<C,E><C,E>

**第五步**：将边<E,G><E,G>加入到最小生成树中

上一步操作后，边<E,G><E,G>的权值最小，故将其加入到最小生成树中

**第六步**： 将边<A,B><A,B>加入到最小生成树中

上一步操作后，边<F,G><F,G>加入

此时，最小生成树构造完成，含有的依次为<E,F><C,D><D,E><B,F><E,G><A,B><E,F><C,D><D,E><B,F><E,G><A,B>

### `Kruskal`算法要点 ###

1.  对图的所有边按照权值大小排序

此问题可通过代码实例理解

*  将边添加到最小生成树中，如何判断是否形成回路
 *  通过记录每个顶点在最小生成树中的终点。终点即在最小生成树中与它连通的最大顶点。每次添加一条边到最小生成树中时，判断该边的两个顶点的终点是否重合，重合则构成回路。
    
    ![Graph\_prim\_G4\_kruskal\_is\_or\_not\_loop][Graph_prim_G4_kruskal_is_or_not_loop]
    
    在将<E,F><C,D><D,E><E,F><C,D><D,E>加入到最小生成树中后，这几条边的顶点就都有了终点
    
     *  `C`的终点是`F`
     *  `D`的终点是`F`
     *  `E`的终点是`F`
     *  `F`的终点是`F`
    
    关于终点，就是将所有顶点按照从小到大的顺序排列好之后；某个顶点的终点就是”与它连通的最大顶点”。 虽然边<C,E><C,E>权值最小，但终点都是`F`， 故会形成回路
    
    ### `Kruskal`算法代码 ###
    
    #### `Edge`边集数组结构 ####
    
        typedef struct
        {
            int begin;
            int end;
            int weight;
        }Edge;
         
         
            
         
         
            
             1 
             2 
             3 
             4 
             5 
             6
    
    #### 算法 ####
    
        /* 生成最小生成树 */
        void MiniSpanTree_Kruskal(MGraph G)
        {
            int i, j, n, m;
            int k = 0;
            int parent[MAXVEX];  /* 定义一数组用来判断边与边是否形成环路 */
            Edge edges[MAXEDGE];  /* 定义边集数组,edge的结构为begin,end,weight,均为整型 */
        
            /* 用来构建边集数组并排序********************* */
            for(i = 0; i < G.numVertexes - 1; i++)
            {
                for(j = i + 1; j < G.numVertexes; j++)
                {
                    if(G.arc[i][j] < INF)
                    {
                        edges[k].begin = i;
                        edges[k].end = j;
                        edges[k].weight = G.arc[i][j];
                        k++;
                    }
                }
            }
            sort(edges, &G);
            /* ******************************************* */
        
            printf("打印最小生成树：\n");
        
            for(i = 0; i < G.numVertexes; i++)
                parent[i] = 0;  /* 初始化数组值为0 */
        
            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中。 表示此顶点已经在生成树集合中*/
                    printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
                }
            }
        
        }
         
         
            
         
         
            
             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
    
    #### 算法源码 ####
    
    [邻接矩阵源码][Link 1]
    
    **参考资料**
    
     *  [Kruskal算法(一)之 C语言详解][Kruskal_ C]

[Graph_prim_G4]: https://img-blog.csdn.net/20180528154306243?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTEyMjE4MjA=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[Graph_prim_G4_kruskal_details]: https://img-blog.csdn.net/20180528154406143?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTEyMjE4MjA=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[Graph_prim_G4_kruskal_is_or_not_loop]: https://img-blog.csdn.net/2018052815442495?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTEyMjE4MjA=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[Link 1]: https://github.com/hao555sky/Play_with_Data_Structures/tree/master/Graph/MCST_Kruskal
[Kruskal_ C]: http://wangkuiwu.github.io/2013/04/12/kruskal-c/