无向图的深度优先和广度优先遍历.docx

#defineM20#include""#include""#include"" typedefstruct{/*定义图*/ intV[M]; intR[M][M]; intvexnum;}Graph; voidcreatgraph(Graph*g,intn){/*创建图*/   inti,j,r1,r2;   g->vexnum=n;   for(i=1;i<=n;i++)/*顶点用i表示*/      {       g->V[i]=i;      }  for(i=1;i<=n;i++)/*初始化R*/  for(j=1;j<=n;j++)      {       g->R[i][j]=0;      } printf("PleaseinputR(0,0END):\n");/*输入R*/ scanf("%d,%d",&r1,&r2); while(r1!=0&&r2!=0)  {   g->R[r1][r2]=1;   g->R[r2][r1]=1;   scanf("%d,%d",&r1,&r2);  }} voidprintgraph(Graph*g){/*打印图的邻接矩阵*/   inti,j;   for(i=1;i<=g->vexnum;i++)   {for(j=1;j<=g->vexnum;j++)       {        printf("%2d",g->R[i][j]);        }     printf("\n");   }} intvisited[M];/*全局变量:访问标志数组*/ voidvisitvex(Graph*g,intvex){/*访问顶点*/   printf("%d",g->V[vex]);} intfirstadjvex(Graph*g,intvex){/*获取第一个未被访问的邻接节点*/   intw,i;   for(i=1;i<=g->vexnum;i++)    {     if(g->R[vex][i]==1&&visited[i]==0)        {         w=i;         break;        }     else         {          w=0;         }    }   returnw;} intnextadjvex(Graph*g,intvex,intw){/*获取下一个未被访问的邻接节点*/   intt;   t=firstadjvex(g,w);   returnt;} voidDFS(Graph*g,intvex){/*深度递归遍历*/   intw;   visited[vex]=1;   visitvex(g,vex);   for(w=firstadjvex(g,vex);w>0;w=nextadjvex(g,vex,w))     if(!visited[w])      {       DFS(g,w);      }} voidDFSTraverse(Graph*g){/*深度遍历*/    inti;    for(i=1;i<=g->vexnum;i++)      visited[i]=0;    for(i=1;i<=g->vexnum;i++)