smalltree.txt

最小生成树的克鲁斯卡尔算法

  #include<stdio.h>   
  #include<stdlib.h>   
  #include<string.h>   
  #define   MAX_NAME   5   
  #define   MAX_VERTEX_NUM   20     
  typedef   char   Vertex[MAX_NAME];/*顶点名字串*/   
  typedef   int   AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接距阵*/   
  struct   MGraph/*定义图*/   
  {   
    Vertex   vexs[MAX_VERTEX_NUM];     
    AdjMatrix   arcs;     
    int   vexnum,arcnum;     
  };   
    
  typedef   struct   
  {     
      Vertex   adjvex;   /*当前点*/   
      int   lowcost;         /*代价*/   
  }minside[MAX_VERTEX_NUM];   
    
  int   LocateVex(MGraph   G,Vertex   u)//定位   
  {     
      int   i;   
      for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vexs[i])==0)return   i;   
      return   -1;   
  }   
    
  void   CreateGraph(MGraph   &G)   
  {   
      int   i,j,k,w;   
      Vertex   va,vb;   
      printf("请输入无向网G的顶点数和边数(以空格为分隔)\n");   
      scanf("%d   %d",&G.vexnum,&G.arcnum);   
      printf("请输入%d个顶点的值(<%d个字符):\n",G.vexnum,MAX_NAME);   
      for(i=0;i<G.vexnum;++i)   /*   构造顶点集*/   
          scanf("%s",G.vexs[i]);   
      for(i=0;i<G.vexnum;++i)   /*初始化邻接矩阵*/   
          for(j=0;j<G.vexnum;++j)   
              G.arcs[i][j]=0x7fffffff;     
      printf("请输入%d条边的顶点1   顶点2   权值(以空格作为间隔):   \n",G.arcnum);   
      for(k=0;k<G.arcnum;++k)   
      {   
          scanf("%s%s%d%*c",va,vb,&w);     
          i=LocateVex(G,va);   
          j=LocateVex(G,vb);   
          G.arcs[i][j]=G.arcs[j][i]=w;   /*对称*/   
      }   
  }   
    void   kruskal(MGraph   G)   
    {   
        int   set[MAX_VERTEX_NUM],i,j;   
        int   k=0,a=0,b=0,min=G.arcs[a][b];   
        for(i=0;i<G.vexnum;i++)   
            set[i]=i;   
        printf("最小代价生成树的各条边为:\n");   
        while(k<G.vexnum-1)     
        {     
            for(i=0;i<G.vexnum;++i)   
                for(j=i+1;j<G.vexnum;++j)   
    if(G.arcs[i][j]<min)   
    {   
        min=G.arcs[i][j];     
        a=i;     
        b=j;     
    }   
            min=G.arcs[a][b]=0x7fffffff;     
            if(set[a]!=set[b])   
            {   
                printf("%s-%s\n",G.vexs[a],G.vexs[b]);     
                k++;     
                for(i=0;i<G.vexnum;i++)   
                    if(set[i]==set[b])     
                        set[i]=set[a];   
            }   
        }   
    }   
    
  int   main()   
    {   
        MGraph   g;   
        CreateGraph(g);     
        kruskal(g);     
        system("PAUSE");   
        return   0;   
    }