这次我记录的是另外一种很有意思的东西——最小生成树。相信学过离散数学的朋友都对这种东西不陌生，那么在代码中，我们该如何实现它呢？接下来，我将对此讲解一些自己的心得。

首先让我们看看什么是最小生成树————一个有n个节点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个节点，并且有保持图连通的最少的边。这是《数据结构与算法分析》中对于最小生成树的描述，用更简便的话来说，就是一个图的每个节点都被链接起来，但是如果任意去掉一个边那么这个图就不是连通的。如果每条边上还有权重的话，那么最小生成树还需要满足所有边的权重之和最少这个条件。因此，最小生成树也是最小权重生成树的简称。而要实现最小生成树我们一般采用Prim算法或者是Kruskal算法来实现，接下来，将对这两种算法进行说明。
注意：最小生成树中的边数为节点数减一，即|V| - 1；

Prim算法的原理是在开始时选取一个节点最为其实节点，然后遍历所有该节点链接的边，并选取其中权重最小的边，同时将已经选取的节点标位已知；接下来重复之前的步骤，在已知节点的链接的边中选取权重最小的边，同时将其所链接的边标位已知，一直这样操作，直到所有的节点都已知。(PS:在实际代码中，我们使用一个表格来储存生成树的信息)
伪代码如下：

void Prim(Node Start) {   
    Node v, w; v = Start;   
    v is known;  
  
    while(have node not be retrieved) {   
    // 更新边信息   
    for each w adjacent to v   
        update information v--w；   
    // 寻找最小权重的边   
    find the least weighted edge v--w && w is unknown;  
    w is known;   
    }  
} 

看看伪代码其实还是很简单的吧。

Kruskal算法的原理其实和Prim算法有很多类似的地方，不过与Prim算法不同，Kruskal算法是在所有的边中选取权重最小的不构成圈的边，直到选取的边数为节点数减一(即VexNum - 1)，这样我们就可以构成一个最生成树了；其中我们需要注意的是如何判断一个节点是否与另外一个节点链接，这里我们就可以使用Union/Find算法进行判断;而对于最小边的选取，我们可以使用优先队列来完成。
注：Union/Find算法，即不相交集算法，用于判断元素是否在同一个集合中；其中Find(x)返回元素x所在的集合，Set(x, y)将x，y所在集合链接在一起。
伪代码如下:

void Kruskal() {  
    int EdgeAccepted = 0;  
    PriorityQueue H;  
    Disjoint_Set S;  
    Node v, w;  
    SetType vSet, wSet;  
    Edge e;  
      
    Read Edges into H;  
  
    while(EdgeAccepted < VexNum) {  
        // 获取权重最小的边  
        E = DeleteMin(H);  
        vSet = S.Find(v), wSet = S.Find(w);  
        // 判断两个顶点是否链接  
        if(vSet != wSet) {  
            S.Set(v, w);  
            EdgeAccepted++;  
        }  
    }  
}

最后，我是用的邻接表的方法来实现的图的链接，所以可能与有些朋友的有所不同；如果大家还对最小生成树有什么疑问，可以留言问我，我也会第一时间回复大家的！
PS：代码中的Union/Find算法是我自己写的，所以可能会和标准库中的有所不同，可以根据自己的需求更改。

最后的最后CSDN博客地址:JZX555的CSDN

参考文献：《数据结构与算法分析——C语言描述》