邻接矩阵的遍历

1、邻接矩阵的遍历#include<stdio.h>#include<stdlib.h>#defineINFINITY999#defineMAX20#defineOK1#defineERROR0typedefcharVRType;typedefenumDG,DN,UDG,UDNGraphKind;typedefstructArcCellintadj;ArcCell,AdjMatrixMAXMAX;typedefstructVRTypevexsMAX;AdjMatrixarcs;intvexnum,arcnum;GraphKindkind;MGraph;typedefstru

2、ctint*front;int*rear;Queue;boolvisitMAX;intt=0;voidCreateGraph(MGraph&G);voidCreate(MGraph&G,inta);intLocateVex(MGraphG,charv);voidDFSTraverse(MGraph&G);voidDFS(MGraph&G,intv);voidBFSTraverse(MGraph&G);voidInitQueue(Queue&Q);voidEnQueue(Queue&Q,intv);voidDeQueue(Queue&

3、;Q,int&u);intQueueEmpty(QueueQ);intvisited(inta);intFirstAdjVex(MGraphG,intv);intNextAdjVex(MGraphG,intv,intw);voidOutput(MGraphG);voidmain()MGraphG;CreateGraph(G);DFSTraverse(G);BFSTraverse(G);Output(G);voidCreateGraph(MGraph&G)inti;printf("nnnnnn");printf("ttt1无printf("

4、ttt2无printf("ttt3有printf("ttt4有scanf("%d",&i);G.kind=(GraphKind)(i);switch(i)case1:system("cls");Create(G,1);break;case2:system("cls");Create(G,2);break;case3:system("cls");Create(G,3);break;case4:system("cls");Create(G,4);break;default

5、:system("cls");system("cls");printf("你的输入有误");voidCreate(MGraph&G,inta)图nnnn");网nnnn");图nnnn");网nnnn");向向向向inti,j,w=1,k;charv1,v2;if(a=1)printf("请输入无向图的顶点数和边数:");elseif(a=2)printf("请输入无向网的顶点数和边数:");elseif(a=3)printf("请输入有

6、向图的顶点数和弧数:");elseprintf("请输入有向网的顶点数和弧数:");scanf("%d%d",&G.vexnum,&G.arcnum);flushall();printf("nnn请输入顶点(字符间不要空格):");for(i=0;i<G.vexnum;i+)scanf("%c",&G.vexsi);system("cls");for(i=0;i<G.vexnum;i+)for(j=0;j<G.vexnum;j+)if(a=1|

7、a=2)G.arcsij.adj=0;elseG.arcsij.adj=999;for(k=0;k<G.arcnum;k+)if(a=1|a=2)printf("请输入边上的两个顶点(字符间不要空格):");elseprintf("请输入弧尾和弧头(字符间不要空格):");flushall();scanf("%c%c",&v1,&v2);flushall();if(a=2|a=4)printf("n请输入这两个顶点之间的权值:");scanf("%d",&w);i=

8、LocateVex(G,v1);j=LocateVex(G,v2);G.arcsij.adj=w;printf("nnn");if(a=1|a=2)G.arcsji.adj=G.arcsij.adj;intLocateVex(MGraphG,charv)inti=0;while(G.vexsi!=v)i+;returni;voidDFSTraverse(MGraph&G)intv;system("cls");printf("邻接矩阵的深度优先搜索结果:");for(v=0;v<G.vexnum;v+)visitv=fal

9、se;for(v=0;v<G.vexnum;v+)if(!visited(v)DFS(G,v);printf("nnnnn");voidDFS(MGraph&G,intv)intw;visitv=true;if(t=1)printf("t=1;for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)if(!visited(w)DFS(G,w);->");printf("%c",G.vexsv);voidBFSTraverse(MGraph&G)intv,u,w;Q

10、ueueQ;for(v=0;v<G.vexnum;v+)visitv=false;InitQueue(Q);printf("邻接矩阵的广度优先搜索结果:");for(v=0;v<G.vexnum;v+)if(!visited(v)visitv=true;printf("%c",G.vexsv);EnQueue(Q,v);while(!QueueEmpty(Q)DeQueue(Q,u);for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w)if(!visited(w)visitw=true;prin

11、tf("EnQueue(Q,w);printf("nnnnn");voidInitQueue(Queue&Q)Q.front=(int*)malloc(MAX*sizeof(int);if(!Q.front)exit(-1);Q.rear=Q.front;voidEnQueue(Queue&Q,intv)*Q.rear+=v;voidDeQueue(Queue&Q,int&u)->%c",G.vexsw);u=*-Q.rear;intQueueEmpty(QueueQ)if(Q.front=Q.rear)return

12、OK;elsereturnERROR;intvisited(inta)if(a<0)returnOK;if(visita)returnOK;elsereturnERROR;intFirstAdjVex(MGraphG,intv)intw;for(w=0;w<G.vexnum;w+)if(G.arcsvw.adj)returnw;return-1;intNextAdjVex(MGraphG,intv,intw)for(w=w+1;w<G.vexnum;w+)if(G.arcsvw.adj)returnw;return-1;voidOutput(MGraphG)inti,j;printf("顶点为:");for(i=0;i<G.vexnum;i+)printf("%c",G.vexsi);printf("nnnnn");printf("顶点之间的关系为:nnnnn");for(i=0;i&l