prim.c

用普里姆(Prim)算法构造最小生成树 数据结构的基本应用

/*  PRIM算法  */
#include<stdio.h>
#include<string.h>

#define INFINITY  10000  /*  最大值10000  */
#define MAX_VERTEX_NUM 20  /*  最大顶点个数  */
#define Status int

typedef enum GraphKind{
    DG,  /*  有向图   */
    DN,  /*  有向网   */
    AG,  /*  无向图   */
    AN  /*  无向网   */
}GraphKind;

typedef struct ArcCell{
    int adj;  /*  adj对无权图用1或0表示是否相邻；对带权图表示权值类型  */
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct{
    char        vexs[MAX_VERTEX_NUM];  /*  顶点向量  */
    AdjMatrix  arcs;  /*  邻接矩阵  */
    int        vexnum,arcnum;  /*  图的当前顶点数和弧数  */
    GraphKind  kind;  /*  图的种类标志  */
}MGraph;

typedef struct{
    char adjvex;
    int lowcost;
}closedge[MAX_VERTEX_NUM];


Status CreateUDC(MGraph *G)
  /*  采用数组（邻接矩阵）表示法，构造无向网G  */
{
  char v1,v2;
  int i,j,k,l,weight;  /*  weight表示边的权值  */

  printf("Please input the number of the vertex and arc:\n");

  printf("vertex:");  /*  输入顶点数  */
  scanf("%d",&G->vexnum);

  printf("arc:");  /*  输入弧数  */
  scanf("%d",&G->arcnum);

  printf("Please input the vertex:");

  getchar();
  for(i=0;i<G->vexnum;i++)  /*  构造顶点向量  */
    G->vexs[i]=getchar();
  for(i=0;i<G->vexnum;i++)  /*  初始化邻接矩阵  */
    for(j=0;j<G->vexnum;j++)
      G->arcs[i][j].adj=INFINITY;

  printf("Please input the two vertexs connecting one arc and the weight of the arc:\n");
  for(k=0;k<G->arcnum;k++)/*  构造邻接矩阵  */
    {
      getchar();
      scanf("%c%c%d",&v1,&v2,&weight);  /*  输入一条边依附的顶点及权值  */
      for(l=0;l<G->vexnum;l++)  /*  确定v1在G中位置  */
        if(v1==G->vexs[l])
          {
            i=l;
            break;
          }
      for(l=0;l<G->vexnum;l++)  /*  确定v2在G中位置  */
        if(v2==G->vexs[l])
          {
            j=l;
            break;
          }
      G->arcs[i][j].adj=weight;  /*  弧<v1,v2>的权值  */
      G->arcs[j][i].adj=G->arcs[i][j].adj;  /*  置<v1,v2>的对称弧<v2,v1>  */
    }
  return 1;
}  /*  CreateUDC()  */


void MinispanTree_PRIM(MGraph *G,char u)
  /*  用prim算法从第u个定点出发构造G的最小生成树T,输出T的各条边  */
{
  int i,j,k;
  closedge close;

  for(i=0;i<G->vexnum;i++)  /*  用k记录u在G中位置  */
    if(u==G->vexs[i])
      {
        k=i;
        break;
      }  /*  if  */
  for(j=0;j<G->vexnum;j++)
    {
      if(j!=k)
        {
          close[j].adjvex=G->vexs[k];  /*  将顶点k放入close[j]  */
          close[j].lowcost=G->arcs[k][j].adj;  /*  将与k连接的邻接边的权值放入close[j].lowcost  */
        }  /*  if  */
    }  /*  for  */
  close[j].lowcost=10000;
  close[j].adjvex='\0';
  close[k].lowcost=0;  /*  初始，U={u}  */
  close[k].adjvex=u;
  for(i=1;i<G->vexnum;i++)  /*  选择其余G->vexnum-1个顶点  */
    {
      k=Minimum(close);  // 求出T的下一个结点：第k顶点  */
      printf("%c",close[k].adjvex);
      printf("--->");
      printf("%c  ",G->vexs[k]);
      printf("%d\n",close[k].lowcost);
      close[k].lowcost=0;  /*  将第k点并入U集  */
      for(j=0;j<G->vexnum;j++)  /*  新顶点并入U后重新选择最小边  */
        {
          if(G->arcs[k][j].adj<close[j].lowcost)
            {
              close[j].adjvex=G->vexs[k];
              close[j].lowcost=G->arcs[k][j].adj;
            }  /*  if  */
        }  /*  for  */
    }  /*  for  */
}  /*  MinispanTree_PRIM()  */



Status Minimum(closedge close)
  /*  从close.lowcost中选出最小的权值所代表的那个没有被并入u的顶点  */
{
  int j1,client,j2;

  j1=0;
  client=10000;
  while(close[j1].adjvex!='\0')
    {
      if(client>close[j1].lowcost&&close[j1].lowcost!=0)
        {
          client=close[j1].lowcost;
          j2=j1;
        }  /*  if  */
      j1++;
    }  /*  while  */
  return j2;
}  /*  Minimum()  */


main()
{
  MGraph *G;
  int i,j;
  
  G=(MGraph*)malloc(sizeof(MGraph));
  CreateUDC(G);
  MinispanTree_PRIM(G,'a');
}