最小生成树.cpp

最小生成树问题

#include<stdio.h>
main()
{
    int sum=0,s=0,r=0,k,l,a,i,j,m,n,c=0,x,y,count=0;
    printf("请依次输入顶点和边的个数:");
    scanf("%d %d",&n,&m);
    int u[n],v[n],t1[n],b[n];
    for(i=0;i<n;i++)
     {u[i]=v[i]=0;
      t1[i]=10240;}
    int tree[n][n];
    int t[n][n];
    for(i=0;i<n;i++)
     for(j=0;j<n;j++)
      {
        tree[i][i]=0;
        t[i][j]=0;
      }
    printf("请输入各边的权:\n");
    for(r=0;r<m;r++)
     {
      scanf("%d %d %d",&i,&j,&x);
      tree[i][j]=tree[j][i]=x;
     }
    u[s]=0;
    for(i=1;i<n;i++)
     v[i]=i;
    v[0]=-1;
    printf("\n最小生成树为:\n");
    while(s!=n-1)
     {
         for(k=0;k<=s;k++)
         {
            for(l=1;l<n;l++)
             {
              if(v[l]!=-1&&tree[u[k]][l]>0)
                 {
                  if(t1[count]>tree[u[k]][l])
                   {
                    t1[count]=tree[u[k]][l];
                    t[0][count]=u[k];
                    t[1][count]=l;
                   }
                 }
             }
         }
        u[s+1]=t[1][count];
        v[t[1][count]]=-1;
        s++;
        c++;
        printf("%d--%d\n",t[0][count],t[1][count]);
        count++;
     }

     for(i=0;i<count;i++)
      sum+=t1[i];
     printf("\n最小生成树的权和为:");
     printf("%d\n",sum);
}