C语言课程设计报告_图的遍历的演示|c语言程序代码编程小程序设计|c语言课程设计报告课程案例
#define M 20#include
#include #include /*定义图*/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; /*顶点用i表示*/ for(i=1;i<=n;i++) { g->V[i]=i; } /*初始化R*/ for(i=1;i<=n;i++) for(j=1;j<=n;j++) { g->R[i][j]=0; } /*输入R*/ printf("Please input R(0,0 END):\n"); 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;/*初始化队列*/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 BESTraverse(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); } } } } }}/*主程序*/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"); BESTraverse(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"); }}
