|
#2
monk026982010-06-03 15:18
|
#include "stdio.h"
#define max 20
typedef int Status;
typedef struct ArcCell{
int adj;
}ArcCell,AdjMatrix[max][max];
typedef struct{
int vexs[max];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph;
struct
{
int adjvex;
int lowcost;
}closedge[max];
Status CreateUDG(MGraph *G){
int i,j,k;
int v1,v2; int w;
printf("shuru dingdianshu and hushu:");
scanf("%d,%d",&G->vexnum,&G->arcnum);
printf("goujian dingdian xiangliang :");
for(i=0;i<G->vexnum;i++)
scanf("%d",&G->vexs[i]);
printf("gouzao linjie juzhen :");
for(i=0;i<G->vexnum;i++)
for(j=0;j<G->vexnum;j++)
G->arcs[i][j].adj=0;
for(k=0;k<G->arcnum;k++){
scanf("%d,%d,%d",&v1,&v2,&w);
i=Locate(*G,v1);
j=Locate(*G,v2);
G->arcs[i][j].adj=w;
G->arcs[j][i]=G->arcs[i][j];
}
return 1;
}
Status Locate(MGraph G,int v){
int i;
for(i=0;i<G.vexnum;i++)
if(v==G.vexs[i]) return i;
return -1;
}
int MinNum(MGraph G)
{
int i,j=0,k=0,min=0;
for(i=0; i<G.vexnum; i++)
if(closedge[i].lowcost!=0)
{
min=closedge[i].lowcost;
k=i;
break;
}
for(j=i+1;j<G.vexnum;j++)
if(closedge[j].lowcost!=0)
{
if(min>=closedge[j].lowcost)
{
min=closedge[j].lowcost;
k=j;
}
}
return k;
}
void MininSpanTreePrim(MGraph G,int V )
{
int k=Locate(G,V);
int j,i;
for(j=0; j<G.vexnum; ++j )
{
if(j!=k)
{
closedge[j].lowcost =G.arcs[k][j].adj;
closedge[j].adjvex=V;
}
}
closedge[k].lowcost = 0;
for(i=1; i<G.vexnum; ++i )
{
k=MinNum(G);
closedge[k].lowcost = 0;
printf("%d--%d ",closedge[k].adjvex,G.vexs[k]);
for(j = 0; j<G.vexnum; ++j )
if( closedge[j].lowcost > G.arcs[k][j].adj )
{
closedge[j].lowcost = G.arcs[k][j].adj;
closedge[j].adjvex=G.vexs[k];
}
}
}
void main()
{
MGraph G; int v;
int i,j;
CreateUDG(&G);
for(i=0;i<G.vexnum;i++){
for(j=0;j<G.vexnum;j++)
printf("%3d",G.arcs[i][j].adj);
printf("\n");
}
printf("shuru dian :");
scanf("%d", &v);
MininSpanTreePrim( G, v );
printf("\n");
}
请高手改正
