图的最小生成树--小白进阶篇

情景导入：

            最近同学小i ，我们姑且叫他小i同学

，他最近不知道迷上了旅游，常常在夜深人静的时候，突然仰天大笑，”明天我要做个惊天地泣鬼神的决定，我要去旅行“ ，然后市面上几乎所有的地图，百科全书啊，什么地理大勘探啊，还有各种省钱的穷游小秘籍,小i同学在女朋友的帮助下，商量了许多可以去参观的旅游城市，包括城市里的各种旅游路线，能重要的是小i有个非常贴心精明的女朋友，他女朋友将小i同学准备去的城市之间所有的路线以及花费的money都一一列出来，聪明的你一定能找到最短的路线吧！那么回归到我们怎么能用代码或者说程序来计算出最短路线呢？ 

            上面就提到了最短问题，当然我们可以用Floyd-warshall 算法 Dijlstra 单源最短路等等， 今天我们来说一个图的最小生成树，那么树 作为计算机一种存储结构，它的优点很多，这里就不列举了。

            一言不合先上代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
// 最小生成树
const int INF = 0x3f3f3f3f ;
const int MAX = 12000 ;
struct edge{
    int u ;
    int v ;
    int w ;
};
struct edge e[MAX] ;
int f[MAX];
bool cmp(const struct edge a ,const struct edge b)
{
    return a.w <b.w ;
}
int Getroot(int v)
{
    if(f[v]==v)
    {
        return v ;
    }
    else
    {
        return f[v] = Getroot(f[v]);
    }
    
    
}
bool merge(int v ,int u)
{
    int t1 = Getroot(v) ;
    int t2 = Getroot(u) ;
    if(t1!=t2)
    {
        f[t2] = t1 ;
        return true ;
    }
    return false ;
    
}
int main()
{
    int sum = 0 ;
    int count = 0 ;
    int n ,m ;
    int i ,j ;
    while(cin>>n>>m)
    {
        sum = 0 ;
        count = 0 ;


    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&e[i].u ,&e[i].v ,&e[i].w);
    }
    sort(e+1,e+1+m,cmp) ;// 对边进行排序;
    // 并查集初始化
    for(i=1;i<=n;i++)
    {
        f[i] = i ;
        
    }
    //  核心代码
    for(i=1;i<=m;i++)
    {
        if(merge(e[i].u ,e[i].v))
        {
            count++;
            sum+=e[i].w;
        }
        if(count == n-1) // n个顶点 有n-1条边
        break;
    }
    if(count !=n-1)
    {
        printf("%d\n",-1);
        
    }
    else
    printf("%d\n",sum);
}
    
    return 0 ;
}

先对各条边进行排序，按照从小到大顺序排序，我们用了STL 标准库里的sort模板函数。

每次取最小的顶点 u 与 v 看看他们之间是否连通 ，若未连通则连通，我们采用了并查集，最后将各个联通的边输出就ok了