最小生成树（MST） prim（) 算法 kruskal（）算法 A

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

Input

测试输入包含若干测试用例。

每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。
Output

对每个测试用例，在1行里输出最小的公路总长度。
Sample Input

Sample Output

3

5

Huge input, scanf is recommended.

下面有一些我写代码时使用到的代码变量：
邻接矩阵（Adjacency Matrix）
无穷大（infinite）
顶点（vertex）
权值（cost）
初始化（initialize）
临时工（temp）
整型最大数值=0x7fffffff
AC代码：
1.prim算法

#include<iostream>

#include<stdio.h>

#define N 110

#define inf 0x7fffffff

int cost[N][N];

int ver[N];

int n,a,b,l,temp,v,k=;

using namespace std;

int initia(){//顶点及储存权值的邻接矩阵的初始化

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++){

                if(i==j) cost[i][j]=;

                else cost[i][j]=inf;

                ver[i]=;

            }

             ver[]=;

             return ;

}

int prim(){

    int sumcost=,mincost;

    int temp,v;

    for(int vsum=1;vsum<n;vsum++)//顶点总数的记录，当所有顶点都被选中时跳出循环

    {

        mincost=inf;//一个标志用于筛选最小权值的判断条件

        for(v=1;v<=n;v++)

        {

            if(ver[v]==)//所有可选顶点起点的筛选

            {

                for(int j=1;j<=n;j++)//遍历所有顶点

                {

                   if(cost[v][j]!=&&cost[v][j]<mincost&&ver[j]!=1)//除去自身及不可达的顶点

                    {

                      mincost=cost[v][j];//选出最小权值

                      temp=j;//记录节点

                    }

                }

            }

          }

        ver[temp]=;//顶点标为已经被选中

        cost[v][temp]=cost[temp][v]=0;//边标志为已经被选中

        sumcost+=mincost;//记录所有路径权值总和

    }

    cout<<sumcost<<endl;

    return ;

}

int main()

{

    while(cin>>n&&n!=){

            initia();

            int t=n*(n-)/;

            while(t--){

                cin>>a>>b>>l;

                cost[a][b]=cost[b][a]=l;

        }

    prim();

    }

    return ;

}

用于记录的数组的下标是从1开始的，且注意红色标记地方，vsum的循环次数不要增加,否则会出错！

这里还有一份其他人的代码，红色部分大大减少了运行时的重复次数，没太看懂！

#include<stdio.h>

#include<iostream>

#define INF 99999999

#define N 110

using namespace std;

int n,G[N][N];

void prim()

{

    int p[N],vis[N],i,j,v,sum,m,last,k =;

    p[k++] = 1;

    sum = ;

    for(i=;i<=n;i++) vis[i]=;

    vis[] = ;

    for(m=;m<n;m++)

    {

        int min = INF;

        for(j=0;j<k;j++)

        {

            v = p[j];

            for(i=;i<=n;i++)

            {

                if(!vis[i]&& G[v][i]<min){

                    min = G[v][i];

                cout<<"cost v"<<v<<"  i"<<i<<":"<<G[v][i]<<endl;

                    last = i;

                 }

            }

        }

        vis[last] = ;

        p[k++] = last;

        sum += min;

    }

    printf("%d\n",sum);

}

int main()

{

    int t,m,i,j,a,b,c;

    while(scanf("%d",&n),n)

    {

        for(i=;i<=n;i++){

            for(j=;j<=n;j++)

            G[i][j] = INF;

        }

        m = n*(n-)/;

        while(m--){

            scanf("%d%d%d",&a,&b,&c);

            if( c<G[a][b] || c<G[b][a] )//去重边

                G[a][b] = G[b][a] = c;

        }

        prim();

    }

    return ;

}

2.kruskal算法

这个代码还没有过，我还在找原因

先存着

#include<iostream>

#include<stdio.h>

#define N 110

#define inf 0x7fffffff

int cost[N][N];

int ver[N];

int n,a,b,l,tempi,tempj;

using namespace std;

int initia(){//顶点及储存权值的邻接矩阵的初始化

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++){

                if(i==j) cost[i][j]=;

                else cost[i][j]=inf;

                ver[i]=;

            }

             return ;

}

int judge(int i,int j){

    if(ver[i]==&&ver[j]==) return ;

    else return ;

}

int kruskal()

{

    int sumcost=,mincost;

    for(int esum=;esum<n-;esum++)//边总数的记录，当边的总数为n-1时跳出循环

    {

        mincost=inf;

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

        if(cost[i][j]!=&&cost[j][i]!=&&cost[i][j]<mincost&&cost[j][i]<mincost&&judge(i,j))//除去自身及不可达的顶点

                    {

                      mincost=cost[i][j];//选出最小权值

                      tempi=i;//记录节点

                      tempj=j;//记录节点

                    }

        ver[tempi]=;//顶点标为已经被选中

        ver[tempj]=;//顶点标为已经被选中

        cost[tempi][tempj]=cost[tempj][tempi]=;//边标志为已经被选中

        sumcost+=mincost;//记录所有路径权值总和

    }

    cout<<sumcost<<endl;

    return ;

}

int main()

{

    while(cin>>n&&n!=){

            initia();

            int t=n*(n-)/;

            while(t--){

                cin>>a>>b>>l;

                cost[a][b]=cost[b][a]=l;

        }

    kruskal();

    }

    return ;

}

巴特西

最小生成树（MST） prim（) 算法 kruskal（）算法 A - 还是畅通工程

最新文章

热门文章