学步园

 //=======================================================================
// Use Adjacency Matrix and Prim algorithm Spanning MiniSpanTree
// BY:CHLAWS   
// TIME:08-8-6
// PS:转载请别删除此备注
//=======================================================================
#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 20 //最大顶点数
typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵类型
typedef char VertexType;
typedef struct  {
 VertexType vexs[MAX_VERTEX_NUM];     //顶点表
 AdjMatrix arcs;                      //邻接矩阵
 int vexnum,arcnum;                   //图的顶点数和弧数
}MGraph;

struct DNode{
 VertexType adjvex;
 int   lowcost;
}closedge[MAX_VERTEX_NUM];

int  LocateVex(MGraph G,char u);
void MiniSpanTree_PRIM(MGraph G,VertexType u);
void CreateMGraph(MGraph &G);
int     mininum(struct DNode closedge[],int vexnum);
void main()
{
 char u;
 MGraph G;
 
 printf("Text/n");
 CreateMGraph(G);
 
 printf("input you will start find first vertex:");
 fflush(stdin);
 scanf("%c",&u);
 
 MiniSpanTree_PRIM(G,u);
}

void MiniSpanTree_PRIM(MGraph G,VertexType u)
{
 int i,j,k;
 k = LocateVex(G,u);
 
 for (j=0; j<G.vexnum; ++j)
 {
  if(j!=k)
  {
   closedge[j].adjvex = u;
   closedge[j].lowcost = G.arcs[k][j];
  }
 }
 closedge[k].lowcost = 0;
 
 for (i=1; i<G.vexnum; ++i)
 {
  k = mininum(closedge,G.vexnum);
  printf("(%c, %c)/n",closedge[k].adjvex,G.vexs[k]);
  closedge[k].lowcost = 0;

  for(j=0; j<G.vexnum; ++j)
  { 
   //这两个if是关键
   //先保证两点间有路径,并且没被选入树的情况
   if((G.arcs[k][j]>0 && closedge[j].lowcost>0) && (G.arcs[k][j]<closedge[j].lowcost))
   {
    closedge[j].adjvex = G.vexs[k];
    closedge[j].lowcost= G.arcs[k][j];
   }//再判断当两点间无直接路径时的情况
   else if(closedge[j].lowcost<0)
   {
    closedge[j].adjvex = G.vexs[k];
    closedge[j].lowcost = G.arcs[k][j];
   }
  }
 }

}

int     mininum(struct DNode closedge[], int vexnum)
{ 
 int min = 10000;
 int pos = -1;
 while(vexnum--)
 { 
  if((closedge[vexnum].lowcost > 0) && (min > closedge[vexnum].lowcost))
  {
   min = closedge[vexnum].lowcost;
   pos = vexnum;
  }
 }
 if(-1 == pos) { printf("closedge.lowcost find error!"); exit(-1); }
 return pos;
}

void CreateMGraph(MGraph &G)
{ 
 int i,j,k,w; 
 char v1,v2;
 printf("Input vexnum & arcnum:");
 scanf("%d,%d",&G.vexnum,&G.arcnum);
 printf("Input Vertices:");
 scanf("%s",G.vexs);
 for (i=0;i<G.vexnum;i++)
  for (j=0;j<G.vexnum;j++)
   G.arcs[i][j]=-1;
 for (k=0;k<G.arcnum;k++)
 {
  printf("Input Arcs(v1->v2 &w):/n");
  fflush(stdin);
  scanf("%c,%c,%d",&v1,&v2,&w);
  i=LocateVex(G,v1);
  j=LocateVex(G,v2);
  G.arcs[i][j]=w;
  G.arcs[j][i]=w;
 }
 return;
}

int LocateVex(MGraph G,char u)
{ 
 int i;
 for (i=0;i<G.vexnum;i++)
 { 
  if (u == G.vexs[i]) return i;
 }
 if (i == G.vexnum)
 {
  printf("Error u!/n");
  exit(1);
 }

 return 0;
}

//测试结果:
/*
Text
Input vexnum & arcnum:6,10
Input Vertices:ABCDEF
Input Arcs(v1->v2 &w):
A,B,6
Input Arcs(v1->v2 &w):
A,C,1
Input Arcs(v1->v2 &w):
A,D,5
Input Arcs(v1->v2 &w):
B,C,5
Input Arcs(v1->v2 &w):
B,E,3
Input Arcs(v1->v2 &w):
C,E,6
Input Arcs(v1->v2 &w):
C,F,4
Input Arcs(v1->v2 &w):
C,D,5
Input Arcs(v1->v2 &w):
D,F,2
Input Arcs(v1->v2 &w):
E,F,6
input you will start find first vertex:A
(A, C)
(C, F)
(F, D)
(C, B)
(B, E)
请按任意键继续. . .

*/