代码随想录算法训练营第 57 天 |53.寻宝（最小生成树）

代码随想录算法训练营

Day57 代码随想录算法训练营第 57 天 |53.寻宝（最小生成树）

前言

prim法

讲解文档

kruskal法

讲解文档

最小生成树解决的问题：将v个点连接起来的最小花费

一、prim法

1.题目链接

53

2.思路

（1）二维矩阵存图
（2）三步法
1）确定当前距离最小生成树最近的点
遍历所有不在最小生成树的点，找到当前距离最小生成树最近的
2）当前距离最小生成树最近的点加入最小生成树
用数组标记点是否在最小生成树里，is_tree[i]=1表示节点i在最小生成树里
3）更新各个点到最小生成树的距离
注：

• 为了把v个点连接起来，需要v-1条边
• 点到最小生成树的距离，是这个点到最小生成树所有节点的距离中的最小值

3.题解

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int v;
    int e;
    cin>>v>>e;
    vector<vector<int>> graph(v+3,vector<int>(v+3,10001));
    //不相连的点认为是无穷远
    std::vector<int>minDis(v+3,10001);
    vector<bool>is_tree(v+3,false);
    int s;
    int t;
    int w;
    for(int i=0;i<e;i++){
        cin>>s>>t>>w;
        graph[s][t]=w;
        graph[t][s]=w;
    }
    for(int i=1;i<v;i++)//链接v-1条线
    {
        int cur=-1;
        int min_dis=10005;
        for(int j=1;j<=v;j++)
        {
            if(!is_tree[j]&&min_dis>minDis[j]){
                min_dis=minDis[j];
                cur=j;
            }
        }
        is_tree[cur]=true;
        for(int k=1;k<=v;k++){
            if(is_tree[k])continue;
            minDis[k]=min(minDis[k],graph[cur][k]);
        }
    }
    int res=0;
    for(int i=2;i<=v;i++)
    {
        res+=minDis[i];
    }
    cout<<res;
    return 0;
}

二、kruskal

1.思路

（1）定义边类型（成员包括端点和长度），边数组存放图
（2）边长排序
（3）遍历边
（4）判断边的两个端点是否有在同一集合内（有共同祖先）：用并查集判断
如果是：那么不连接（如果链接就会成环）
如果不是：那么链接，加入最小生成树（加入结果，本题不用标记是否加入最小生成树），并且加入并查集

2.题解

#include<bits/stdc++.h>
using namespace std;
vector<int>father(10001,0);
struct edge{
    int l;
    int r;
    int val;
};
const bool cmp(edge e1,edge e2)
{
    return e1.val<e2.val;
}
int find(int x){
    if(x==father[x]){
        return x;
    }
    father[x]=find(father[x]);
    return father[x];
}
int main()
{
    int v;
    int e;
    cin>>v>>e;
    vector<edge>edges;
    for(int i=1;i<=v;i++){
        father[i]=i;
    }
    int left;
    int right;
    int val;
    for(int i=0;i<e;i++){
        cin>>left>>right>>val;
        edges.push_back({left,right,val});
    }
    sort(edges.begin(),edges.end(),cmp);
    int res=0;
    for(int i=0;i<e;i++)
    {
        int l_root=find(edges[i].l);
        int r_root=find(edges[i].r);
        if(l_root!=r_root){
            father[l_root]=r_root;
            res+=edges[i].val;
        }
    }
    cout<<res;
    return 0;
}

总结

本质都是贪心
prim维护点：遍历点，每次加入最近的点
kruskal维护边：将所有的边排序，遍历边，优先加入短的边，每次连接时先判断连上以后是否成环