NC159 题解 | #最小生成树#

题意分析

给出一张图，图上有n个节点，m条路，现在，我们需要计算将所有的点构成一个连通图所需要的最小的代价，题目会给出某两个结点之间的成本，需要我们最小化总的成本。

思路分析

我们首先很明确的知道这个就是需要我们求出图上的一棵最小生成树。我们发现，我们可以还是按照求单源最短路的思想去求解。其实求一棵最小生成树，就类似于我们将图上面的n个结点汇聚成一个点，这里也可以看作是一个集合，就是原来的图上有n个集合，现在我们需要将n个集合转化为一个集合。这里我们还是按照一个贪心的思想去求解。我们发现，为了使最后的代价最小化，我们只需要找尽可能小的边去连接我们这些结点，但是我们需要注意的是，如果某一个时刻某一些结点已经在一个集合里面了，那么我们同一个集合里面的相连的边不能继续计算了。这其实很好理解，如果这两个结点A和B都在同一个集合里面了，此时我们在添加一条边C就没有必要了，这条边C如果我们计算到最后的结果里面对答案没有任何的贡献。反之，我们只需要计算那些不在同一个集合里面相连的边就行了。

解法一 Prim算法+堆优化

这里我们按照单源最短路的思想，我们需要将最后的结点都汇聚到1号结点所在的集合，当我们进行扩展的时候，我们遇到一个不和1在同一个集合的结点的时候，我们就累加这个结点到1号结点所在集合的权值到最后的答案里面。当然，这个过程中我们利用堆维护了我们每次取的时候都是取的权值尽可能小的边。这样不断扩展下去就可以得到最后的结果了。
代码如下
- 利用堆优化的时间复杂度为 $O (n l o g n)$ ,我们每次遍历的时候只需要遍历那些没有被访问过的点，被访问过的点不会再次被遍历。
- 过程中使用了d数组维护到每个点到1号结点所在集合的最短的距离，用vis进行标记，用vector数组存储图，所以总的时间复杂度为O(n)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    int d[5010];
    bool vis[5010]={false};
    const int INF=1e9;
    vector<pair<int,int> > v[5010];
    int Dijkstra(int n){
        fill(d,d+5010,INF);
        d[1]=0; // 起始点的位置
        int ans=0;
        for(int i=1;i<=n;i++){
            int u=-1,MIN=INF;
            // 找到目前没有遍历过的最短的位置
            for(int j=1;j<=n;j++){
                if(vis[j]==false&&d[j]<MIN){
                    u=j;
                    MIN=d[j];
                }
            }
            
            if(u==-1) return -1;
            vis[u]=true;
            ans+=d[u];
            
            // 更新这个点相连的位置的距离
            for(auto x:v[u]){
                int y=x.first;
                if(vis[y]==false&&x.second<d[y]){
                   d[y]=x.second;
                }
            }
        }
        return ans;
    }
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        // write code here
        // 我们先进行存储整个图的情况
        for(int i=0;i<m;i++){
            v[cost[i][0]].push_back(make_pair(cost[i][1],cost[i][2]));
            v[cost[i][1]].push_back(make_pair(cost[i][0],cost[i][2]));
        }
        return Dijkstra(n);
    }
};

解法二 kurskal算法

该算法主要是通过从整体进行一个贪心的策略，检查所有的边，找出权最小的边进行存储。但是，还有两个前提：
- 如果加入这条边之后与已经加入的边形成一个连通图，也就是会形成环，那么就不能把这条边加入。
- 如果此时的边的数量等于结点数量-1的话，那么就可以直接退出循环了。
主要需要解决的是两个问题：
- 怎么确定加上这条边后会不会是一个连通图？这个可以用之前学过的并查集先进行处理，然后后面要用到的时候再进行判断。
- 如何保存我们的加入的边？还是用到并查集，通过并查集中的合并的函数来进行处理。
举例说明，如下图就是在一个图上求最小生成树的求解过程
代码如下
- 在这个过程中，我们需要存储所有的边的情况，将所有的边按照从小到大进行排序，然后利用并查集合并。时间复杂度为 $O (M l o g M)$ , $M$ 为图的边数
- 过程中我们需要额外开数组存储边的情况，同时利用并查集维护不同的集合的元素，所以总的空间复杂度为 $O (n)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    struct node{
        int x,y; // 表示路径的两个结点
        int z;// 表示路径的权值
        // 重载小于运算符，将权值小的放到前面
        bool operator < (const node &a){
            return z<a.z;
        }
    }Node[50010];
    int fa[5010];
    // 并查集查找父节点
    int get(int x){
        if(x==fa[x]) return x;
        return fa[x]=get(fa[x]);
    }
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        // write code here
        // 存储图的情况
        for(int i=0;i<m;i++){
            Node[i].x=cost[i][0];
            Node[i].y=cost[i][1];
            Node[i].z=cost[i][2];
        }
        // 按照边权进行排序
        sort(Node,Node+m);
        for(int i=1;i<=n;i++){
            fa[i]=i;
        }
        int sum=0;
        for(int i=0;i<m;i++){
            int fx=get(Node[i].x);
            int fy=get(Node[i].y);
            // 如果这两个结点不是在同一个集合里面，那么就合并
            if(fx!=fy){
                fa[fx]=fy;
                sum+=Node[i].z;
            }
        }
        return sum;
    }
};