図の隣接テーブル記憶
18329 ワード
/* c7-2.h */
#define MAX_VERTEX_NUM 20
typedef enum{DG,DN,AG,AN}GraphKind; /* { , , , } */
typedef struct ArcNode
{
int adjvex; /* */
struct ArcNode *nextarc; /* */
InfoType *info; /* ） */
}ArcNode; /* */
typedef struct
{
VertexType data; /* */
ArcNode *firstarc; /* , */
}VNode,AdjList[MAX_VERTEX_NUM]; /* */
typedef struct
{
AdjList vertices;
int vexnum,arcnum; /* */
int kind; /* */
}ALGraph;
/* bo7-2.c ( c7-2.h ) (15 ) */
int LocateVex(ALGraph G,VertexType u)
{ /* : G ,u G */
/* : G u, ; -1 */
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vertices[i].data)==0)
return i;
return -1;
}
Status CreateGraph(ALGraph *G)
{ /* , G( 4 ) */
int i,j,k;
int w; /* */
VertexType va,vb;
ArcNode *p;
printf(" ( :0, :1, :2, :3): ");
scanf("%d",&(*G).kind);
printf(" , : ");
scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);
printf(" %d (<%d ):
",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* */
{
scanf("%s",(*G).vertices[i].data);
(*G).vertices[i].firstarc=NULL;
}
if((*G).kind==1||(*G).kind==3) /* */
printf(" ( ) 、 ( ):
");
else /* */
printf(" ( ) ( ):
");
for(k=0;k<(*G).arcnum;++k) /* */
{
if((*G).kind==1||(*G).kind==3) /* */
scanf("%d%s%s",&w,va,vb);
else /* */
scanf("%s%s",va,vb);
i=LocateVex(*G,va); /* */
j=LocateVex(*G,vb); /* */
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
if((*G).kind==1||(*G).kind==3) /* */
{
p->info=(int *)malloc(sizeof(int));
*(p->info)=w;
}
else
p->info=NULL; /* */
p->nextarc=(*G).vertices[i].firstarc; /* */
(*G).vertices[i].firstarc=p;
if((*G).kind>=2) /* , */
{
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=i;
if((*G).kind==3) /* */
{
p->info=(int*)malloc(sizeof(int));
*(p->info)=w;
}
else
p->info=NULL; /* */
p->nextarc=(*G).vertices[j].firstarc; /* */
(*G).vertices[j].firstarc=p;
}
}
return OK;
}
void DestroyGraph(ALGraph *G)
{ /* : G 。 : G */
int i;
ArcNode *p,*q;
(*G).vexnum=0;
(*G).arcnum=0;
for(i=0;i<(*G).vexnum;++i)
{
p=(*G).vertices[i].firstarc;
while(p)
{
q=p->nextarc;
if((*G).kind%2) /* */
free(p->info);
free(p);
p=q;
}
}
}
VertexType* GetVex(ALGraph G,int v)
{ /* : G ,v G 。 : v */
if(v>=G.vexnum||v<0)
exit(ERROR);
return &G.vertices[v].data;
}
Status PutVex(ALGraph *G,VertexType v,VertexType value)
{ /* : G ,v G */
/* : v value */
int i;
i=LocateVex(*G,v);
if(i>-1) /* v G */
{
strcpy((*G).vertices[i].data,value);
return OK;
}
return ERROR;
}
int FirstAdjVex(ALGraph G,VertexType v)
{ /* : G ,v G */
/* : v 。 G , -1 */
ArcNode *p;
int v1;
v1=LocateVex(G,v); /* v1 v G */
p=G.vertices[v1].firstarc;
if(p)
return p->adjvex;
else
return -1;
}
int NextAdjVex(ALGraph G,VertexType v,VertexType w)
{ /* : G ,v G ,w v */
/* : v ( w ) 。 */
/* w v , -1 */
ArcNode *p;
int v1,w1;
v1=LocateVex(G,v); /* v1 v G */
w1=LocateVex(G,w); /* w1 w G */
p=G.vertices[v1].firstarc;
while(p&&p->adjvex!=w1) /* p w */
p=p->nextarc;
if(!p||!p->nextarc) /* w w */
return -1;
else /* p->adjvex==w */
return p->nextarc->adjvex; /* v ( w ) */
}
void InsertVex(ALGraph *G,VertexType v)
{ /* : G ,v */
/* : G v( , InsertArc() ) */
strcpy((*G).vertices[(*G).vexnum].data,v); /* */
(*G).vertices[(*G).vexnum].firstarc=NULL;
(*G).vexnum++; /* G 1 */
}
Status DeleteVex(ALGraph *G,VertexType v)
{ /* : G ,v G */
/* : G v */
int i,j;
ArcNode *p,*q;
j=LocateVex(*G,v); /* j v */
if(j<0) /* v G */
return ERROR;
p=(*G).vertices[j].firstarc; /* v */
while(p)
{
q=p;
p=p->nextarc;
if((*G).kind%2) /* */
free(q->info);
free(q);
(*G).arcnum--; /* 1 */
}
(*G).vexnum--; /* 1 */
for(i=j;i<(*G).vexnum;i++) /* v */
(*G).vertices[i]=(*G).vertices[i+1];
for(i=0;i<(*G).vexnum;i++) /* v */
{
p=(*G).vertices[i].firstarc; /* 1 */
while(p) /* */
{
if(p->adjvex==j)
{
if(p==(*G).vertices[i].firstarc) /* 1 */
{
(*G).vertices[i].firstarc=p->nextarc;
if((*G).kind%2) /* */
free(p->info);
free(p);
p=(*G).vertices[i].firstarc;
if((*G).kind<2) /* */
(*G).arcnum--; /* 1 */
}
else
{
q->nextarc=p->nextarc;
if((*G).kind%2) /* */
free(p->info);
free(p);
p=q->nextarc;
if((*G).kind<2) /* */
(*G).arcnum--; /* 1 */
}
}
else
{
if(p->adjvex>j)
p->adjvex--; /* ( ) */
q=p;
p=p->nextarc;
}
}
}
return OK;
}
Status InsertArc(ALGraph *G,VertexType v,VertexType w)
{ /* : G ,v w G */
/* : G <v,w>, G , <w,v> */
ArcNode *p;
int w1,i,j;
i=LocateVex(*G,v); /* */
j=LocateVex(*G,w); /* */
if(i<0||j<0)
return ERROR;
(*G).arcnum++; /* G 1 */
if((*G).kind%2) /* */
{
printf(" ( )%s→%s : ",v,w);
scanf("%d",&w1);
}
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
if((*G).kind%2) /* */
{
p->info=(int*)malloc(sizeof(int));
*(p->info)=w1;
}
else
p->info=NULL;
p->nextarc=(*G).vertices[i].firstarc; /* */
(*G).vertices[i].firstarc=p;
if((*G).kind>=2) /* , */
{
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=i;
if((*G).kind==3) /* */
{
p->info=(int*)malloc(sizeof(int));
*(p->info)=w1;
}
else
p->info=NULL;
p->nextarc=(*G).vertices[j].firstarc; /* */
(*G).vertices[j].firstarc=p;
}
return OK;
}
Status DeleteArc(ALGraph *G,VertexType v,VertexType w)
{ /* : G ,v w G */
/* : G <v,w>, G , <w,v> */
ArcNode *p,*q;
int i,j;
i=LocateVex(*G,v); /* i v( ) */
j=LocateVex(*G,w); /* j w( ) */
if(i<0||j<0||i==j)
return ERROR;
p=(*G).vertices[i].firstarc; /* p v */
while(p&&p->adjvex!=j) /* p <v,w> */
{ /* p */
q=p;
p=p->nextarc;
}
if(p&&p->adjvex==j) /* <v,w> */
{
if(p==(*G).vertices[i].firstarc) /* p 1 */
(*G).vertices[i].firstarc=p->nextarc; /* */
else
q->nextarc=p->nextarc; /* */
if((*G).kind%2) /* */
free(p->info);
free(p); /* */
(*G).arcnum--; /* 1 */
}
if((*G).kind>=2) /* , <w,v> */
{
p=(*G).vertices[j].firstarc; /* p サ */
while(p&&p->adjvex!=i) /* p <w,v> */
{ /* p */
q=p;
p=p->nextarc;
}
if(p&&p->adjvex==i) /* <w,v> */
{
if(p==(*G).vertices[j].firstarc) /* p 1 */
(*G).vertices[j].firstarc=p->nextarc; /* */
else
q->nextarc=p->nextarc; /* */
if((*G).kind==3) /* */
free(p->info);
free(p); /* */
}
}
return OK;
}
Boolean visited[MAX_VERTEX_NUM]; /* ( ) */
void(*VisitFunc)(char* v); /* ( ) */
void DFS(ALGraph G,int v)
{ /* v G。 7.5 */
int w;
VertexType v1,w1;
strcpy(v1,*GetVex(G,v));
visited[v]=TRUE; /* TRUE( ) */
VisitFunc(G.vertices[v].data); /* v */
for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w))))
if(!visited[w])
DFS(G,w); /* v w DFS */
}
void DFSTraverse(ALGraph G,void(*Visit)(char*))
{ /* G 。 7.4 */
int v;
VisitFunc=Visit; /* VisitFunc, DFS */
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE; /* */
for(v=0;v<G.vexnum;v++)
if(!visited[v])
DFS(G,v); /* DFS */
printf("
");
}
typedef int QElemType; /* */
#include"c3-2.h"
#include"bo3-2.c"
void BFSTraverse(ALGraph G,void(*Visit)(char*))
{/* G。 Q visited。 7.6 */
int v,u,w;
VertexType u1,w1;
LinkQueue Q;
for(v=0;v<G.vexnum;++v)
visited[v]=FALSE; /* */
InitQueue(&Q); /* Q */
for(v=0;v<G.vexnum;v++) /* , v=0 */
if(!visited[v]) /* v */
{
visited[v]=TRUE;
Visit(G.vertices[v].data);
EnQueue(&Q,v); /* v */
while(!QueueEmpty(Q)) /* */
{
DeQueue(&Q,&u); /* u */
strcpy(u1,*GetVex(G,u));
for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w))))
if(!visited[w]) /* w u */
{
visited[w]=TRUE;
Visit(G.vertices[w].data);
EnQueue(&Q,w); /* w */
}
}
}
printf("
");
}
void Display(ALGraph G)
{ /* G */
int i;
ArcNode *p;
switch(G.kind)
{
case DG: printf("
");
break;
case DN: printf("
");
break;
case AG: printf("
");
break;
case AN: printf("
");
}
printf("%d ：
",G.vexnum);
for(i=0;i<G.vexnum;++i)
printf("%s ",G.vertices[i].data);
printf("
%d ( ):
",G.arcnum);
for(i=0;i<G.vexnum;i++)
{
p=G.vertices[i].firstarc;
while(p)
{
if(G.kind<=1) /* */
{
printf("%s→%s ",G.vertices[i].data,G.vertices[p->adjvex].data);
if(G.kind==DN) /* */
printf(":%d ",*(p->info));
}
else /* ( ) */
{
if(i<p->adjvex)
{
printf("%s－%s ",G.vertices[i].data,G.vertices[p->adjvex].data);
if(G.kind==AN) /* */
printf(":%d ",*(p->info));
}
}
p=p->nextarc;
}
printf("
");
}
}
/* algo7-2.c 7.9 */
#include"c1.h"
typedef int VRType;
typedef char InfoType;
#define MAX_NAME 3 /* +1 */
#define MAX_INFO 20 /* +1 */
typedef char VertexType[MAX_NAME];
#include"c7-1.h"
#include"bo7-1.c"
typedef struct
{ /* U V-U */
VertexType adjvex;
VRType lowcost;
}minside[MAX_VERTEX_NUM];
int minimum(minside SZ,MGraph G)
{ /* closedge.lowcost */
int i=0,j,k,min;
while(!SZ[i].lowcost)
i++;
min=SZ[i].lowcost; /* 0 */
k=i;
for(j=i+1;j<G.vexnum;j++)
if(SZ[j].lowcost>0)
if(min>SZ[j].lowcost)
{
min=SZ[j].lowcost;
k=j;
}
return k;
}
void MiniSpanTree_PRIM(MGraph G,VertexType u)
{ /* u G T, T 7.9 */
int i,j,k;
minside closedge;
k=LocateVex(G,u);
for(j=0;j<G.vexnum;++j) /* */
{
if(j!=k)
{
strcpy(closedge[j].adjvex,u);
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
closedge[k].lowcost=0; /* ,U={u} */
printf(" :
");
for(i=1;i<G.vexnum;++i)
{ /* G.vexnum-1 */
k=minimum(closedge,G); /* T ： K */
printf("(%s-%s)
",closedge[k].adjvex,G.vexs[k]); /* */
closedge[k].lowcost=0; /* K U */
for(j=0;j<G.vexnum;++j)
if(G.arcs[k][j].adj<closedge[j].lowcost)
{ /* U */
strcpy(closedge[j].adjvex,G.vexs[k]);
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
}
void main()
{
MGraph G;
CreateAN(&G);
MiniSpanTree_PRIM(G,G.vexs[0]);
}
/* main7-2.c bo7-2.c */
#include"c1.h"
#define MAX_NAME 3 /* +1 */
typedef int InfoType; /* */
typedef char VertexType[MAX_NAME]; /* */
#include"c7-2.h"
#include"bo7-2.c"
void print(char *i)
{
printf("%s ",i);
}
void main()
{
int i,j,k,n;
ALGraph g;
VertexType v1,v2;
printf("
");
CreateGraph(&g);
Display(g);
printf(" ， ：");
scanf("%s%s",v1,v2);
DeleteArc(&g,v1,v2);
printf(" ， : ");
scanf("%s%s",v1,v2);
PutVex(&g,v1,v2);
printf(" ， : ");
scanf("%s",v1);
InsertVex(&g,v1);
printf(" ， : ");
scanf("%d",&n);
for(k=0;k<n;k++)
{
printf(" : ");
scanf("%s",v2);
printf(" ， (0: 1: ): ");
scanf("%d",&j);
if(j)
InsertArc(&g,v2,v1);
else
InsertArc(&g,v1,v2);
}
Display(g);
printf(" ， : ");
scanf("%s",v1);
DeleteVex(&g,v1);
Display(g);
printf(" :
");
DFSTraverse(g,print);
printf(" :
");
BFSTraverse(g,print);
DestroyGraph(&g);
printf(" , ,
");
for(i=0;i<3;i++) /* 3 */
{
CreateGraph(&g);
Display(g);
printf(" ， : ");
scanf("%s",v1);
InsertVex(&g,v1);
printf(" ， : ");
scanf("%d",&n);
for(k=0;k<n;k++)
{
printf(" : ");
scanf("%s",v2);
if(g.kind<=1) /* */
{
printf(" ， (0: 1: ): ");
scanf("%d",&j);
if(j)
InsertArc(&g,v2,v1);
else
InsertArc(&g,v1,v2);
}
else /* */
InsertArc(&g,v1,v2);
}
Display(g);
printf(" ， : ");
scanf("%s",v1);
DeleteVex(&g,v1);
Display(g);
DestroyGraph(&g);
}
}