分别采用邻接矩阵、邻接表存储结构实现图的遍历.doc

#define INFINITY 0#define INF32767#define MAX_NUM 20#define MAXV 100#includetypedef char VRType;typedef enumDG=1,DN,UDG,UDNGraphKind;typedef struct ArcCell VRType adj;ArcCell *info;AdjMatrixMAX_NUMMAX_NUM;typedef struct VRType vexsMAX_NUM;AdjMatrix arcs;int vexnum,arcnum;GraphKind kind;MGraph;void PRIN(MGraph &G);int LocateVex(MGraph &G,VRType v1);int FirstAdjVex(MGraph &G,int v);int NextAdjVex(MGraph &G,int v,int w);void CreateUDN(MGraph &G)int i,j,k,w; VRType v1,v2; G.kind =UDN; printf(构造无向网n);printf(G.vexnum:); scanf(%d,&G.vexnum );printf(G.arcnum:); scanf(%d,&G.arcnum );getchar();for(i=0;iG.vexnum ;i+)printf(G.vexs%d:,i);sscanf(%c,&G.vexs i);getchar();for(i=0;iG.vexnum ;+i)for(j=0;jG.vexnum ;+j)G.arcs ij.adj =INFINITY;G.arcs =NULL; for(k=0;kG.vexnum ;+k) printf(v1(char):); scanf(%c,&v1);getchar();printf(v2(char):); scanf(%c,&v2);getchar();printf(w(int):); scanf(%d,&w);getchar();i=LocateVex(G,v1); j=LocateVex(G,v2); G.arcs ij.adj=w; G.arcs ji.adj=G.arcs ij.adj; int LocateVex(MGraph &G,VRType v1)int i;for(i=0;iG.vexnum ;i+) if(v1=G.vexs i)return i;return -i;void CreateDN(MGraph &G)int i,j,k,w; VRType v1,v2;G.kind =DN;printf(构造有向网n);printf(G.vexnum:); scanf(%d,&G.vexnum );printf(G.arcnum:); scanf(%d,&G.arcnum );getchar();for(i=0;iG.vexnum ;i+)printf(G.vexs%d:,i);scanf(%c,&G.vexs i);getchar();for(i=0;iG.vexnum ;+i)for(j=0;jG.vexnum ;+j)G.arcs ij.adj =INFINITY;G.arcs =NULL; for(k=0;kG.vexnum ;+k) printf(v1(char):); scanf(%c,&v1);getchar();printf(v2(char):); scanf(%c,&v2);getchar();printf(w(int):); scanf(%d,&w);getchar();i=LocateVex(G,v1); j=LocateVex(G,v2); G.arcs ij.adj=w; void CreateDG(MGraph &G)int i,j,k; VRType v1,v2;G.kind=DG;printf(构造有向网n);printf(G.vexnum:); scanf(%d,&G.vexnum );printf(G.arcnum:); scanf(%d,&G.arcnum );getchar();for(i=0;iG.vexnum ;i+)printf(G.vexs%d:,i); scanf(%c),&G.vexs i; getchar();for(i=0;iG.vexnum ;+i)for(j=0;jG.vexnum ;+j)G.arcs ij.adj =INFINITY;G.arcs =NULL;for(k=0;kG.arcnum ;+k)printf(v1(char):); scanf(%c,&v1);getchar();printf(v2(char):); scanf(%c,&v2);getchar();i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcsij.adj=1;void CreateUDG(MGraph&G)int i,j,k;VRType v1,v2;G.kind=UDG;printf(构造无向图n);printf(G.vexnum:);scanf(%d,&G.vexnum);printf(G.arcnum:);scanf(%d,&G.arcnum);getchar();for(i=0;iG.vexnum;i+)printf(G.vexs%d:,i);scanf(%c,&G.vexsi);getchar();for(i=0;iG.vexnum;+i) for(j=0;iG.vexnum;+j)G.arcsij.adj=INFINITY;G.=NULL; for(k=0;i=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);void DFSTraverse(MGraph &G,int v)int i;for(i=0;iG.vexnum;+i)visitedi=false;for(i=0;iG.vexnum;+i)DFS(G,v);int FirstAdjVex(MGraph&G,int v)int i,w; for(i=0;iG.vexnum;+i)if(G.arcsvi.adj!=0)w=i;break;return w;void PRIN(MGraph&G)int i,j;for(i=0;iG.vexnum;+i) for(j=0;iG.vexnum;+j) printf(%5d,G.arcsii.adj);printf(n);void BFSTraverse(MGraph &G,int v)int queueMAX_NUM,front=0,rear=0;int i,w,u;for(i=0;iG.vexnum;+i)visitedi=false;for(i=0;i=0;w=NextAdjVex(G,u,w)if(!visitedw)visitedw=true;printf(%4c,G.vexsw);rear=(rear+1)%MAX_NUM;queuerea