最小生成树-蒲公英云

最小生成树

有n个城市，m条道路，现在输入n到m的道路的长度，用最少的边将图连接，输出让图连接的最小值

这道题我研究了好长时间才把答案看明白，现在给大家分享一下

具体代码如下

#include<iostream>
using namespace std;
struct edge
{
    int u;
    int v;
    int w;
};//用一个结构体来保存从城市u到城市v的距离w 
struct edge e[10];//有小于10条路 
int n,m;//定义n个城市，m条路  
int f[7]={0},sum=0,count=0;
void quicksort(int left,int right)
{
    int i,j;
    struct edge t;//定义一个中间转换变量 
    if(left>right)//如果左边大于右边结束 
    return;
    i=left;//i等于左，j等于右 
    j=right;
    while(i!=j)
    {
        while(e[j].w>=e[left].w&&i<j)//e[left].w是基准数 
        j--;//往左走 
        while(e[i].w<=e[left].w&&i<j)
        i++;//往右走 
        if(i<j)//交换两个数的位置 
        {
            t=e[i];
            e[i]=e[j];
            e[j]=t;
        }
    }
    //将基准数归位 
    t=e[left];
    e[left]=e[i];
    e[i]=t;
    quicksort(left,i-1);//继续往左递归处理 
    quicksort(i+1,right);// 继续往右递归处理 
    return;
}
//查并集寻找祖先的函数 
int getf(int v)
{
    if(f[v]==v)
    return v;
    else
    {
        f[v]=getf(f[v]);
        return f[v]; 
    }
}
//并查集合并两子集合的函数 
int merge(int v,int u)//v表示出发城市，u表示到达城市 
{
    int t1,t2;
    t1=getf(v);
    t2=getf(u);
    if(t1!=t2)
    {
        f[t2]=t1;
        return 1;
    }
    return 0;
}
int main()
{
     int i;//定义一个循环变量
     cin>>n>>m;//输入一共有n个城市，m条路 
     for(i=1;i<=m;i++)
     cin>>e[i].u>>e[i].v>>e[i].w;//输入从第u个城市到第v个城市的距离w 
     quicksort(1,m);//用快速排序的方式按距离从小到大枚举出1到m条边 
     for(i=1;i<=n;i++)//并查集初始化 
     f[i]=i;
     //Kruskal算法核心部分代码 
     for(i=1;i<=m;i++)//枚举从小到大的每一条边 
     {
         //判断一条边的两个顶点是否已经连通，即判断是否在统一集合中 
         if(merge(e[i].u,e[i].v))//如果目前不连接，则选这条边 
         {
             count++;
             sum=sum+e[i].w;
         }
         if(count==n-1)//选用n-1条边，跳出循环 
         break;
     }
     cout<<sum<<endl;//输出最短距离 
     return 0;
}