sy7_4.c

数据结构实验与学习指导

/*用prim算法构造最小生成树*/
#include <stdio.h>
#include "conio.h"
#define VERTEX_MAX 20 /*最大顶点数*/
typedef char Vextype;
typedef struct        /*邻接矩阵存储表示*/
{
  Vextype vexs[VERTEX_MAX];   /*顶点信息*/
  int adj[VERTEX_MAX][VERTEX_MAX];       /*邻接矩阵存储 */
  int vexnum,arcnum;    /*顶点数、边数*/
} MGraph;
typedef struct
{ Vextype adjvex;       /*依附于最小权值的顶点*/
  int lowcost;         /*最小权值*/
}closedge[VERTEX_MAX];  
int vn,em   ;/*实际图中的顶点数和边数*/
void creat_MGraph(MGraph *Gn);
int  LocatVex(MGraph Gn,Vextype v0);
int  Mininum(closedge dge);
void Prim(MGraph Gn,Vextype v0);
void creat_MGraph(MGraph  *Gn)   /*网络的存储实现：邻接矩阵*/
{
    int i,j,k;
    int w;
    printf("请输入顶点数和边数:");
    scanf("%d,%d",&vn,&em);
    Gn->vexnum=vn;
    Gn->arcnum=em;
    printf("请输入顶点信息:");  /*一个字符*/
    scanf("%s",Gn->vexs);
    for (i=0;i<vn;i++)        /*初始化邻接矩阵*/
      for (j=0;j<vn;j++)
        Gn->adj[i][j]=32767;
    printf("请输入两个顶点间的边和权值(i,j,w):\n");
            /*输入边的顶点和权值*/
    for (k=0;k<em;k++)        /*根据边的顶点对邻接矩阵进行赋值*/
    {
        scanf("%d,%d,%d",&i,&j,&w);
        Gn->adj[i][j]=w;
        Gn->adj[j][i]=w;
    }
    printf("创建成功!\n");
    for (i=0;i<vn;i++)        /*输出邻接矩阵*/
     { for (j=0;j<vn;j++)
       printf("%d  ",Gn->adj[i][j]);
       printf("\n");
      }
    }/* creat_MGraph */
void Prim(MGraph Gn,Vextype v0)  /*Prim算法，从V0出发构造图的最小生成树*/
{ closedge dge;
  int i,j,k;
  k=LocatVex(Gn,v0);        /* 查找V0顶点序号 */
  printf("%c->U  ",v0);      /*V0并入U集合*/
  for(j=0;j<vn;j++)
  if(j!=k)
  {
    dge[j].adjvex=v0;
    dge[j].lowcost=Gn.adj[k][j];
   }
  dge[k].lowcost=0;           /*初始U={V0}*/
  for(i=0;i<vn-1;i++)
  { for(j=0;j<vn;j++)          /*输出dge数组*/
     printf("dge[%d]=%d  ",j,dge[j].lowcost);
     k=Mininum(dge);         /*求权值最小的边*/
     printf(" 最小值min=%d(%c,%c)\n",dge[k].lowcost,dge[k].adjvex,Gn.vexs[k]);
         /*输出最小值及所对应的边*/
    printf("%c->U  ",Gn.vexs[k]); /*顶点进入U集合*/
    dge[k].lowcost=0;             /*顶点Vk入U*/
    for(j=0;j<vn;j++)             /*调整V-U集合中各顶点的lowcost*/
     if (Gn.adj[k][j]<dge[j].lowcost)
     { dge[j].lowcost=Gn.adj[k][j];
       dge[j].adjvex=Gn.vexs[k];
     }/*if*/
  }
} /* Prim*/
int LocatVex(MGraph Gn,Vextype v0)   /* 查找V0顶点序号 */
 { int i;
   for(i=0;i<vn;i++)
   { if(Gn.vexs[i]==v0)
     return i;
   }
}/*  LocatVex*/
int Mininum(closedge dge)   /*从U.V-U集合中查找权值最小的边*/
{ int i,j;
  int min;
  for(i=0;i<vn;i++)
   if(dge[i].lowcost!=0)
     break;
  min=i;
  for(j=0;j<vn;j++)
   if(dge[j].lowcost!=0 && dge[j].lowcost<dge[min].lowcost)
    min=j;
   return min;
}/* Mininum */
void main()
{  char v0;
  MGraph g;
 creat_MGraph(&g);
  printf("请输入起始顶点V0(# 退出):");
  getchar();
  scanf("%c",&v0);
  while (v0!='#')  /*输入#退出*/
  { Prim(g,v0);
    printf("\n");
    printf("请输入起始顶点V0(# 退出):");
    getchar();
    scanf("%c",&v0);
  }
} /*main*/