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

#define M 20 #include "stdio.h" #include "stdlib.h" #include "malloc.h" typedef struct{/*定义图*/ int V[M]; int R[M][M]; int vexnum; }Graph; void creatgraph(Graph *g,int n){/*创建图*/ int i,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("Please input R(0,0 END):\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); } } void printgraph(Graph *g){/*打印图的邻接矩阵*/ int i,j; for(i=1;i<=g->vexnum;i++) { for(j=1;j<=g->vexnum;j++) { printf("%2d ",g->R[i][j]); } printf("\n"); } } int visited[M];/*全局变量:访问标志数组*/ void visitvex(Graph *g,int vex){/*访问顶点*/ printf("%d ",g->V[vex]); } int firstadjvex(Graph *g,int vex){/*获取第一个未被访问的邻接节点*/ int w,i; for(i=1;i<=g->vexnum;i++) { if(g->R[vex][i]==1&&visited[i]==0) { w=i; break; } else { w=0; } } return w; } int nextadjvex(Graph *g,int vex,int w){/*获取下一个未被访问的邻接节点*/ int t; t=firstadjvex(g,w); return t; } void DFS(Graph *g,int vex){/*深度递归遍历*/ int w; visited[vex]=1; visitvex(g,vex); for(w=firstadjvex(g,vex);w>0;w=nextadjvex(g,vex,w)) if(!visited[w]) { DFS(g,w); } } void DFSTraverse(Graph *g){/*深度遍历*/ int i; for(i=1;i<=g->vexnum;i++) visited[i]=0; for(i=1;i<=g->vexnum;i++) if(!visited[i]) { DFS(g,i); } } typedef struct{/*定义队列*/ int V[M]; int front; int rear; }queue; void Initqueue(Queue *q){/*初始化队列*/ q->front=0; q->rear=0; } int Quempty(Queue *q){/*判断队列是否为空*/ if(q->front==q->rear) { return 0; } else { return 1; } } Enqueue(Queue *q,int e){/*入队操作*/ if((q->rear+1)%M==q->front) { printf("The queue is overflow!\n"); return 0; } else { q->V[q->rear]=e; q->rear=(q->rear+1)%M; return 1; } } Dequeue(Queue *q){/*出队操作*/ int t; if(q->front==q->rear) { printf("The queue is empty!\n"); return 0; } else { t=q->V[q->front]; q->front=(q->front+1)%M; return t; } } void BFSTraverse(Graph *g){/*广度遍历*/ int i; queue *q=(Queue *)malloc(sizeof(Queue)); for(i=1;i<=g->vexnum;i++) { visited[i]=0; } Initqueue(q); for(i=1;i<=g->vexnum;i++) { if(!visited[i]) { visited[i]=1; visitvex(g,g->V[i]); Enqueue(q,g->V[i]); while(!Quempty(q)) { int u,w; u=Dequeue(q); for(w=firstadjvex(g,u);w>0;w=nextadjvex(g,u,w)) { if(!visited[w]) { visited[w]=1; visitvex(g,w); Enqueue(q,w); } } } } } } int main()/*主程序*/ { int n; Graph *g=(Graph *)malloc(sizeof(Graph)); char menu; printf("Please input the number of vertex:\n"); scanf("%d",&n); creatgraph(g,n); printf("This is the linjiejuzhen of graph:\n"); printgraph(g); input: printf("Please input B or D or Q ,Breadth_first: B Depth_first: D quit: Q\n"); while((menu=getchar())=='\n'); if(menu=='B') { printf("Breadth_first:\n"); BFSTraverse(g); printf("\n"); goto input; } else if(menu=='D') { printf("Depth_first:\n"); DFSTraverse(g); printf("\n"); goto input; } else if(menu=='Q') { exit(0); } else { printf("Input error!Please input B or D!\n"); } return 0; }