最小生成树

定义

最小生成树（Minimum Spanning Tree，MST）是一个连通图的极小连通子图，它包含图中所有顶点，且所有边的权值之和最小。

即用最小的边连接所有的顶点，使得图连通。符合一下两个条件：
覆盖所有的顶点
边的权值之和最小

Kruskal 算法

中心思想

Kruskal 算法是一种贪心算法，它的思想是每次从所有边中选择一条最小的边，如果这条边不会形成环，那么就将这条边加入到最小生成树中，否则就舍弃这条边。

将所有边按照权值从小到大排序
依次从小到大取出边，如果这条边不会形成环（并查集，判断这条边的两边顶点是否在同一连通块，是则为有环），那么就将这条边加入到最小生成树中，否则就舍弃这条边。
重复步骤 2 直到所有的边都被取出或者最小生成树中已经有 n-1 条边了。

伪代码：

KRUSKAL(G)
    Edges = ∅
    for each vertex v in G.V  //把每个顶点作为一个连通块
        MAKE-SET(v) 
    scan all edges by non-decreasing weight
    for each edge (u, v) in G.E
        if FIND-SET(u) != FIND-SET(v)  //如果这条边的两个顶点不在同一个连通块
            Edges = Edges ∪ {(u, v)}  //把这条边加入到最小生成树中
            UNION(u, v)  //把这两个顶点合并到一个连通块
    return Edges

Kruskal 算法的时间复杂度是 O(ElogE)，其中 E 是边的数量。适用于稀疏图。（稀疏图：边的数量远小于顶点的数量）

Prim 算法

中心思想

Prim 算法是一种贪心算法，它的思想是每次从所有顶点中选择一个最小的顶点，如果这个顶点不会形成环，那么就将这个顶点加入到最小生成树中，否则就舍弃这个顶点。

从图中任意选择一个顶点作为起始顶点，将这个顶点加入到最小生成树中。
依次从小到大取出边，如果这条边不会形成环（并查集，判断这条边的两边顶点是否在同一连通块，是则为有环），那么就将这条边加入到最小生成树中，否则就舍弃这条边。
重复步骤 2 直到所有的边都被取出或者最小生成树中已经有 n-1 条边了。

伪代码：

PRIM(G, r)
    Edges = ∅，
    for each vertex v in G.V  // 
        MAKE-SET(v) 
    for each vertex v in G.V  //初始化每个顶点和树的距离 为无穷大
        v.key = ∞
    r.key = 0  //把起始顶点的 key 设置为 0
    Q = G.V  //把所有顶点加入到优先队列中
    while Q != ∅
        u = EXTRACT-MIN(Q)  //从优先队列中取出 key 最小的顶点
        if u.pi != NIL
            Edges = Edges ∪ {(u.pi, u)}  //把这条边加入到最小生成树中
        for each vertex v in G.Adj[u]  //遍历 u 的邻接顶点
            if v ∈ Q and w(u, v) < v.key  //如果 v 在 Q 中并且 u-v 的权值小于 v 的 key (因为u被纳入到树中，所以要更新 u的邻接顶点的 距离最小生成树的距离)
                v.pi = u  
                v.key = w(u, v)  
    return Edges

Prim和Kruskal不同点

Prim算法和Kruskal算法都是用来求解最小生成树的算法。最小生成树是图中所有边权之和最小的生成树。

Prim算法是从一个顶点开始，不断扩展边权最小的边，直到所有顶点都被加入到树中。它的基本思想是从一个顶点出发，构建最小生成树的过程是不断地选择最小边，并且加入新的顶点。

相比之下，Kruskal算法是从边权最小的边开始，不断加入新的边，直到所有顶点都被加入到树中。它的基本思想是从边权最小的边出发，构建最小生成树的过程是不断地选择边权最小的边，并且加入新的顶点。

两种算法的主要区别在于它们的构建方式不同：Prim算法从一个顶点开始，而Kruskal算法从一条边开始。因此，它们在求解最小生成树时可能会得到不同的结果。