最小生成树 | srcrs

TIP

最近老师在讲贪心算法的应用，最小生成树是其中最经典的应用之一，有时候知道其中的思想，但是用代码实现起来还是很有差距的，中午弄了几个小时prim算法建最小生成树，但是最后还是没搞懂其中的关键，最后无法判断两个点是否是连通的，决定以后就用Kruskal来解决这类问题吧。

# 迷之想法

中午用vector版本邻接表存储的无向图，我的想法是这样的，对每一个顶点域邻接的部分从小到大排序，这样求一个顶点到邻接点的最短距离直接取第一个点就好，等用完了这个点，就将它从该位置移除，与此同时，还要将它的主对角线对称位置也移除，就这样一步步运行下去，但是到最后，还是判断不了添加完的的多个点是否是连通状态，结果就卡在这了。

# 迷之代码

# 采用存储的方式

const int Max=1e4+2;
typedef struct EdgeNode
{
    int to;
    int w;
};
vector<EdgeNode> s[Max];//存储方式
vector<bool> f;

# 输入的方式

int n,m;
    cin >> n >> m;//n代表点数,m代表边数
    for(int k=0;k<m;k++){
        int i,j,w;
        cin >> i >> j >> w;
        EdgeNode e;
        e.to=j;
        e.w=w;
        s[i].push_back(e);
        e.to=i;
        s[j].push_back(e);
    }

# 对邻接点按权值从小到大排序

bool cmp(EdgeNode x,EdgeNode y)
{
    return x.w<y.w;
}
for(int i=1;i<=n;i++){
        sort(s[i].begin(),s[i].end(),cmp);
    }

# 处理并入点过程

    int v=0;
    vector<int> E;
    E.push_back(1);
    f[1]=true;
    while(v!=5){
        int key=0;
        for(int i=0;i<E.size();i++){
            if(s[E[key]][0].w>s[E[i]][0].w){
                key=i;//找到已并入的点的最近点
            }
        }
        f[s[E[key]][0].to]=true;//声明此点已被使用
        E.push_back(s[E[key]][0].to);//将该点并入
        cout <<"选："<< E[key] << ' ' << s[E[key]][0].to << ' ' << s[E[key]][0].w << endl;
        int j=0;
        for(;j<s[s[E[key]][0].to].size();j++){
            if(s[s[E[key]][0].to][j].to==E[key]){
                break;
            }
        }//找到它关于主对角线的点
        s[s[E[key]][0].to].erase(s[s[E[key]][0].to].begin()+j);
        s[E[key]].erase(s[E[key]].begin());//删除
        v++;
    }
        for(int i=1;i<=n;i++){
        for(auto it=s[i].begin();it!=s[i].end();it++){
            EdgeNode e=*it;
            cout << i << ' ' << e.to << ' ' << e.w << endl;
        }
    }

记录下来，以后发现能解决了，再办它。

# 构建最小生成树

prim算法建造最小生成树的时间复杂度是O(n^2),而Kruskal的时间复杂度是eloge，当边比较少时用Kruskal效率会很好，以后边多的时候，也用它凑合着用吧，因为它主要消耗的时间就是排序，排完序后一切都好说，还有就是并查集了。

# 例题

假设有6个顶点，10条边，6个顶点分别用1，2，3，4，5，6表示，边的输入x y w起点、终点、权值，问其中一颗最小生成树的组合，并求它的权值。 输入如下

# 代码如下

#include<bits/stdc++.h>
using namespace std;
const int Max=1e4+2;
int f[Max];
int e=0;//代表此刻边的数目
int sum=0;//权值之和
typedef struct EdgeNode
{
    int from;
    int to;
    int w;
};
vector<EdgeNode> s;
void build(int n)
{
    for(int i=1;i<=n;i++){
        f[i]=i;
    }
}
bool cmp(EdgeNode x,EdgeNode y)
{
    return x.w<y.w;
}
int Find(int w)
{
    return f[w]==w?w:f[w]=Find(f[w]);
}
bool che(int from,int to)
{
    return Find(from)==Find(to);
}
void mer(int from,int to,int p)
{
    if(!che(from,to)){
        f[f[from]]=f[to];
        sum+=s[p].w;
        cout << "边有:" << from << ' ' << to << ' ' << s[p].w << endl;
        e++;
    }
}
int main()
{
    int n,m;
    cin >> n >> m;
    build(n);
    for(int k=0;k<m;k++){
        int i,j,w;
        cin >> i >> j >> w;
        EdgeNode g;
        g.from=i;
        g.to=j;
        g.w=w;
        s.push_back(g);
    }
    sort(s.begin(),s.end(),cmp);
    int p=0;
    while(e!=n-1){
        mer(s[p].from,s[p].to,p);//将边一个个送入去尝试
        p++;
    }
    cout << "最小权值为：" << sum;
    return 0;
}