stree.txt

图的最小生成树

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>
#define ING 9999
int visited[10];/*访问标志数组*/
typedef struct ArcCell{
 int adj;/*顶点关系类型，用1表示相邻，0表示不相邻*/
}ArcCell,**AdjMatrix;/*邻接矩阵*/
typedef struct type{ 
 char data[3];/*顶点值*/
}VertexType;
typedef struct{
 VertexType *vexs;/*顶点向量*/
 AdjMatrix arcs;/*邻接矩阵*/
 int vexnum,arcnum;/*图的顶点数和边数*/
}MGraph;
struct clos{
 VertexType adjvex;
 int lowcost;
}*closedge;/*辅助数组，low..为0时就表示已访问过*/
void InitGraph(MGraph *G)/*初始图*/
{ int i,nu,mu;
 printf("\n输入顶点的个数和（边）弧的个数：");
  scanf("%d%d",&nu,&mu);
  G->arcs=(ArcCell **)malloc(nu*sizeof(ArcCell *));
  for(i=0;i<nu;i++)/*分配邻接矩阵空间*/
      G->arcs[i]=(ArcCell *)malloc(nu*sizeof(ArcCell));
  G->vexs=(VertexType *)malloc(nu*sizeof(VertexType));/*分配顶点空间*/
  G->vexnum=nu;G->arcnum=mu;/*图的顶点数和边数*/
}
void InsertGraph(MGraph *G,int i,VertexType e)/*给图顶点向量付值*/
{ if(i<0||i>G->vexnum) return;
  strcpy(G->vexs[i].data,e.data);
}
int Locate(MGraph G,VertexType v1)/*确定v1在图顶点中的位置*/
{ int i;
 for(i=0;i<G.vexnum;i++)
   if(strcmp(v1.data,G.vexs[i].data)==0) return i;
  return -1;
}
void CreateUND(MGraph *G)/*采用数组（邻接矩阵）*/
{int i,j,k,*p,d,w;
 VertexType v1,v2;
 p=(int *)malloc(G->vexnum*sizeof(int)); 
 for(i=0;i<10;i++) p[i]=0;
 for(i=0;i<G->vexnum;++i)/*初始邻接表*/
 { for(j=0;j<G->vexnum;++j) G->arcs[i][j].adj=ING;}
 printf("按顺序输入顶点和它们的权值再顶点：如 'v1 3 v2' : \n");
 for(k=0;k<G->arcnum;++k)
 {printf("输入第 %d 条（边）弧: \n",k+1);
  scanf("%s%d%s",v1.data,&w,v2.data);/*输入相邻的两个点值和权值*/
  i=Locate(*G,v1);j=Locate(*G,v2);/*用i 和j来确定它们的位置*/
  G->arcs[i][j].adj=w;
  G->arcs[j][i].adj=G->arcs[i][j].adj;/*有向图时就不用这个*/
 }
}
int minimum(MGraph G,struct clos *closedge)/*求出辅助数组中除0之外最小权值的顶点位置*/
{int i,min,j,k;
 for(i=0;i<G.vexnum;i++)/*找出第一个不为0的权值给min*/
  if(closedge[i].lowcost!=0)
  {min=closedge[i].lowcost;k=i;break;}
 for(j=i+1;j<G.vexnum;j++)/*后面其它出现除0外比min小的*/
  if(closedge[j].lowcost!=0)/*就换min值和位置*/
  { 
    if(min>=closedge[j].lowcost) 
    {min=closedge[j].lowcost;k=j;}
  }
 return k;
}
void MiniSpanTree(MGraph G,VertexType u)/*从第U个顶点出发构造最小生成树，输出各条边*/
{int k,j,i;
 closedge=(struct clos *)malloc(G.vexnum*sizeof(struct clos));/*为数组分配空间*/
 k=Locate(G,u);/*U的位置*/
 for(j=0;j<G.vexnum;j++)/*初始化数组*/
  if(j!=k)
  {strcpy(closedge[j].adjvex.data,u.data);
   closedge[j].lowcost=G.arcs[k][j].adj;}
 closedge[k].lowcost=0;/*此时U={u}，表示不用访问它*/
 for(i=1;i<G.vexnum;++i)/*选择其它个顶点*/
 {k=minimum(G,closedge);/*求出T的下一个结点，第K个顶点*/
  printf("  %s , %s  \n",closedge[k].adjvex.data,G.vexs[k].data);/*输出生成树的边*/
  closedge[k].lowcost=0;/*第K个顶点并入U集*/
  for(j=0;j<G.vexnum;++j)
   /*对新进来的点跟其它顶点的权小于以前那些的权则对closedge.low..换值*/
 if(G.arcs[k][j].adj<closedge[j].lowcost)
  {strcpy(closedge[j].adjvex.data,G.vexs[k].data);
   closedge[j].lowcost=G.arcs[k][j].adj;
  }
 }
}
void Pint(MGraph G)/*输出邻接矩阵*/
{int i,j;
 for(i=0;i<G.vexnum;i++)
 {
   for(j=0;j<G.vexnum;j++)
   {if(G.arcs[i][j].adj!=ING)
   printf(" %d ",G.arcs[i][j].adj);
    else printf(" ∞ ");
   }
      printf("\n");
 }
}
void main()
{ MGraph G;
 VertexType e;
 int i;
 InitGraph(&G);
 for(i=0;i<10;i++) visited[i]=0;/*初始为0，表示没被访问过*/
 printf("顶点值： \n");
 for(i=0;i<G.vexnum;++i)/*给图顶点向量付值*/
 {scanf("%s",e.data);InsertGraph(&G,i,e);}
  CreateUND(&G);/*构造图结构*/
  printf("邻接矩阵为：\n");
  Pint(G);/*输出邻接矩阵*/
  printf("\n输入顶点来做树根：");
  scanf("%s",e.data);
  printf("输出成树的所有边：\n");
  MiniSpanTree(G,e);/*从e开始构造最小生成树*/
  getch();
}