最小生成树

                                         最小生成树的入门

最小生成树就是能将所有点都连起来的最短路的和（我的理解）；

看看实例：

有n个城市，给你m条道路；6 92 4 113 5 134 6 35 6 42 3 64 5 71 2 13 4 91 3 2
求出将所有点都连起来的道路总和的最小值；
（1）第一种方法（Kruskal)
利用并查集的思想（不会的先看看并查集）
看代码（有注释）
#include<stdio.h>struct edge{    int u,v,w;//u代表一个端点，v代表另一个端点，w代表权值；}e[10];//用结构体记录每条路的端点和权值；int n,m;int f[7]={0},sum=0,coun=0;//数组f记录每个点的祖宗是谁，sum记录路的长度，coun记录有多少个点在生成树中；//快排，将边的权值从小到大排序；void quicksort(int left,int right){    int i,j;    struct edge t;    if(left>right)        return ;    i=left;    j=right;    while(i!=j)    {        while(e[j].w>=e[left].w&&i<j)            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 ;}//getf是寻找这个点的祖宗是谁，并更新每个点的祖宗；int getf(int v){    if(f[v]==v)        return v;    else    {        f[v]=getf(f[v]);        return f[v];    }}//查看v,u两点是否为一个祖宗，如果不是，就改为一个祖宗；int merge(int v,int u){    int t1=getf(v);    int t2=getf(u);    if(t1!=t2)    {        f[t2]=t1;        return 1;    }    return 0;}int main(){    int i;    scanf("%d%d",&n,&m);    for(i=1;i<=m;i++)//存储每条边的信息；        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);    quicksort(1,m);//对每条边进行排序，按权值从小到大排；    for(i=1;i<=n;i++)//数组初始化，刚开始每个点的祖宗都是自己；        f[i]=i;    for(i=1;i<=m;i++)//遍历每条边；    {        //查看是否为一个祖宗；        //如果是一个祖宗，说明已经进入一个生成树中，就不需要再加了；        //如果不是一个祖宗，就让他进入生成树，并加上他的权值；        if(merge(e[i].u,e[i].v))        {            coun++;//有一个新的点进入生成树；            sum=sum+e[i].w;//加上权值；        }        if(coun==n-1)//如果此时所有的点已经都进入了生成树中，说明已经经过了所有的点；            break;    }    PRintf("%d/n",sum);//输出最小的和；    return 0;}（2）第二种方法（Prim）
就是用最短路的Dijkstra的方法找最短的边；（时间复杂度较高）
#include<stdio.h>#define inf 0x3f3f3f3fint n,m;int map[10][10];//跟最短路一样，存储边的信息，记住是无向图；int dis[10],xia[10];//非常重要：dis是记录最短的边长（从一个点到这个点的边长，而不是从起点到这点的最短路径）；//xia是记录那个点已经连接到了；int main(){    int i,j;    while(~scanf("%d%d",&n,&m))    {        int sum=0,count=0;//sum记录最短的路程，count记录有几个点被链接了；        for(i=1;i<=n;i++)//初始化；        {            for(j=1;j<=n;j++)            {               if(i==j) map[i][j]=0;               else map[i][j]=inf;            }        }        for(i=1;i<=m;i++)//存储边的信息，与最短路的存储方式一样；        {            int a,b,c;            scanf("%d%d%d",&a,&b,&c);            map[a][b]=map[b][a]=c;//无向图；        }        for(i=1;i<=n;i++)//初始化；        {            dis[i]=map[1][i];            xia[i]=0;        }        xia[1]=1;//因为初始化时，已经将与1相连的边的信息存入了dis中；        count++;        int min,x;        while(count<n)        {            min=inf;            for(i=1;i<=n;i++)//找出最短边的另一个顶点，用x记录；                if(xia[i]==0&&dis[i]<min)                    min=dis[x=i];            xia[x]=1;//标记一下；            count++;            sum+=dis[x];            for(i=1;i<=n;i++)//将与x相连的点的边长存入dis中（以前存的是最短路，此时存的是边长）；                if(xia[i]==0&&dis[i]>map[x][i])//这条边必须是两顶点没有被标记过的，标记过的不算；                    dis[i]=map[x][i];        }        printf("%d/n",sum);    }    return 0;}
（3）按照自己的理解写的（供自己看）
#include<stdio.h>#include<algorithm>using namespace std;#include<queue>int n,m;struct node{    int s,e,w;    friend Operator <(node n1,node n2)    {        return n1.w>n2.w;    }} edge[100];int main(){    int i,j;    while(~scanf("%d%d",&n,&m))    {        priority_queue<node>q;        for(i=1; i<=m; i++)        {            scanf("%d%d%d",&edge[i].s,&edge[i].e,&edge[i].w);            if(edge[i].s==1||edge[i].e==1)                q.push(edge[i]);        }        int sum=0,countt=0;        node n1;        int xia[100]= {0};        xia[1]=1;        while(!q.empty())        {            n1=q.top();            if(countt==n)                break;            q.pop();            if(xia[n1.s]==0||xia[n1.e]==0)            {                sum+=n1.w;                countt++;                int x;                if(xia[n1.s]==0)                    xia[x=n1.s]=1;                else                    xia[x=n1.e]=1;                for(i=1; i<=m; i++)                {                    if(edge[i].s==x||edge[i].e==x)                        q.push(edge[i]);                }            }        }        printf("%d/n",sum);    }    return 0;}