一、最小生成树的prim算法和Kruskal算法的区别

Kruskal算法（克鲁斯卡算法）

Kruskal算法是一种贪心算法，我们将每个edge按照权重大小进行排序，每次从边集中取出权重最小且两个顶点都不在同一个集合的边加入生成树中！注意：如果这两个顶点都在同一集合内，说明已经通过其他边相连，因此如果将这个边添加到生成树中，那么就会形成环！这样反复做，直到所有的节点都连接成功！

在这个算法中，最重要的一环就是判断两个节点在不在同一个集合内，很多人想，那你直接用一个set来保存不就好了？这是思路显然不行，因为假设A和其他三个节点相连，同属一个集合，而B和另外三个节点相连，同属一个集合，那么我们将A和B取并集时，是将这两组数据合并一起的，如果使用set，那么当数据量大时还需要遍历，复杂度就会很高，因此使用并查集就会效率快很多了！

并查集详解和STL中的自定义哈希

​mp.weixin.qq.com/s/gGCQ9uqlNQYbBHtw83xgOw

对所有节点遍历建立并查集，按照边的权重建立最小堆

取出最小堆堆顶数据，并判断两端节点是否在同一集合

如不在，则将这两个节点添加到同一集合，接着将边加入生成边，如在，则不进行操作，为无效边

重复上面的操作，直到所有的边都检查完

unordered_set kruskalMST(Graph graph){

    auto cmp = [](const Edge& a, const Edge& b){

        return a.weight > b.weight;    // 最小堆

    };

    vector list;

    for(auto ite: graph.nodes){

        list.push_back(ite.second);

    }

    UnionFindSet unionFind(list);   // 建立并查集

    priority_queue, decltype(cmp)> smallQueue(cmp);

    for(auto edge: graph.edges){

        smallQueue.push(*edge);

    }

    // 构造选中的输出边集

    unordered_set result;

    while(!smallQueue.empty()){

        Edge edge = smallQueue.较好();

        smallQueue.pop();

        if(!unionFind.isSameSet(edge.from, edge.to)){ 

// 判断是否为一个环，如果一个边的两端节点为一个集合，那么必为一个闭合环

            result.insert(edge);

            unionFind.Union(edge.from, edge.to);

        }

    }

    return result;

}

Prim算法（普里姆算法）

Prim算法是另一种贪心算法，和Kuskral算法的贪心策略不同，Kuskral算法主要对边进行操作，而Prim算法则是对节点进行操作，每次遍历添加一个点，这时候我们就不需要使用并查集了。具体步骤为：

建立边set用来存放结果，建立节点set用来存放节点同时用于标记是否被访问过，建立边的最小堆

开始遍历所有节点，如果没有访问，则添加到节点set，然后将其相连的边入堆。

从堆中取最小的边，然后判断to节点是否被访问过，如果没有，将这个边加入生成树（我们想要的边），并标记该节点访问。

然后将to节点所相连的边添加到最小堆中，不然这个网络就不会向外扩展了（这个步骤是必须的）。

循环上面的操作，直到所有的节点遍历完。

注意：对于单连通，从一个节点出发就可以直接找到完整的最小生成树，因此最外的for循环也可以为一个顺序结构，但多连通，就需要从不同的节点出发了！！！

unordered_set primMST(Graph graph){

    // 装边的最小堆

    auto cmp = [](const Edge& e1, const Edge& e2){

        return e1.weight > e2.weight;

    };

    priority_queue, decltype(cmp)> smallQueue(cmp);

    // 判断节点是否访问过

    unordered_set node_set;

    unordered_set result;

    for(auto ite: graph.nodes){

        if(node_set.find(*ite.second) == node_set.end()){

            // 如果没有访问,将其标记为访问过，并把它对应的边放入最小堆

            node_set.insert(*ite.second);

            for(Edge* edge: ite.second->edges){

                smallQueue.push(*edge);

            }

            // 在当前这个图中寻找最小生成树

            while(!smallQueue.empty()){

                // 从堆中取出一个最小权重边，并取出对应节点

                Edge help_edge = smallQueue.较好();

                smallQueue.pop();

                Node edge_to = *(help_edge.to);

                // 然后判断这个节点是否被访问过，如果没有则将这个边加入边集

                if(node_set.find(edge_to) == node_set.end()){

                    result.insert(help_edge);

                    node_set.insert(edge_to);   // 标记edge_to也已经访问过了

                    for(Edge *newEdge: edge_to.edges){

                        smallQueue.push(*newEdge);

                    }

                }

            }

        }

    }

    return result;

}

那么对于这两种算法，我们应该用哪种呢？记得某个人说过这句话，算法没有优劣，每个算法都有它的使用场景，在对的场合使用对的算法，这才是算法工程师应该做的事情！

由于Kruksal算法是对边进行操作，先取出边，然后判断边的两个节点，这样的话，如果一个图结构非常的稠密，那么Kruksal算法就比较慢了，而Prim算法只是对节点进行遍历，并使用set进行标记，因此会相对于Kruksal算法，在稠密图方面好很多，因此Kruksal算法常用于稀疏图，而Prim算法常用于稠密图！

延伸阅读：

二、什么是最小生成树

在给定一张无向图，如果在它的子图中，任意两个顶点都是互相连通，并且是一个树结构，那么这棵树叫做生成树。当连接顶点之间的图有权重时，权重之和最小的树结构为最小生成树！

在实际中，这种算法的应用非常广泛，比如我们需要在n个城市铺设电缆，则需要n-1条通信线路，那么我们如何铺设可以使得电缆最短呢？最小生成树就是为了解决这个问题而诞生的！

上一篇

堆和树有什么区别?

下一篇

树堆（Treap）和红黑树（RB-Tree）各有哪些优劣?