5_3.rar_图的遍历

#include<stdio.h> #include<malloc.h> #include<stdlib.h> #define MAX 30 typedef struct QNode { int data; struct QNode *next; }QNode; typedef struct { QNode *rear; QNode *front; }LinkQueue; void InitQueue(LinkQueue *Q) { Q->front =Q->rear =(QNode *)malloc(sizeof(QNode)); Q->front ->next =NULL; } void EnQueue(LinkQueue *Q,int v) { QNode *p; p=(QNode *)malloc(sizeof(QNode)); p->data =v; p->next =NULL; Q->rear ->next =p; Q->rear =p; } void DeQueue(LinkQueue *Q,int *v) { QNode *p; if(Q->front ==Q->rear ) return; p=Q->front ->next ; *v=p->data ; Q->front ->next =p->next ; if(Q->rear ==p) Q->rear =Q->front ; free(p); } typedef struct EdgeNode { int ivex,jvex; struct EdgeNode *ilink,*jlink; }EdgeNode; typedef struct VexNode { int markV; char info;//顶点信息 int num;//顶点编号 EdgeNode *firstedge; }VexNode; typedef struct { VexNode adjlist[MAX]; int vexnum,edgenum; }Graph; //初始化 void Initilized(Graph *graph) { graph=(Graph *)malloc (sizeof(Graph)); graph->vexnum =0; graph->edgenum =0; } //创建图 void CreateGraph(Graph *graph) { EdgeNode *p,*q,*e; int i; printf("请输入连通无向图的顶点个数和边的条数：\n"); scanf("%d %d",&graph->vexnum,&graph->edgenum); while(graph->vexnum>MAX||graph->edgenum >(graph->vexnum *(graph->vexnum -1)/2)) { printf("输入有误，请重新输入顶点数与边的条数！\n"); scanf("%d%d",&graph->vexnum ,&graph->edgenum ); } for(i=1;i<=graph->vexnum;i++) { printf("请输入第%d个顶点的信息：\n",i); scanf("%s",&graph->adjlist [i].info ); graph->adjlist [i].num =i; graph->adjlist[i].firstedge=NULL; graph->adjlist [i].markV =0; } for(i=1;i<=graph->edgenum;i++) { p=(EdgeNode *)malloc(sizeof(EdgeNode)); printf("请输入每条边依附的两个顶点(用顶点的编号表示)\n"); printf("规定输入顺序：编号小的在前，例如：1 2；1 3；2 3；\n"); scanf("%d %d",&p->ivex,&p->jvex); while(p->ivex ==p->jvex||p->ivex<1||p->ivex >graph->vexnum ||p->jvex <1||p->jvex >graph->vexnum ) { printf("输入的顶点有误，请重新输入!\n"); scanf("%d%d",&p->ivex,&p->jvex); } p->ilink =p->jlink =NULL; if(graph->adjlist [p->ivex ].firstedge==NULL ) graph->adjlist [p->ivex ].firstedge =p; else { q=graph->adjlist [p->ivex ].firstedge ; while(q!=NULL) { e=q; if(q->ivex ==p->ivex ) q=q->ilink ; else q=q->jlink ; } if(e->ivex ==p->ivex ) e->ilink =p; else e->jlink =p; } if(graph->adjlist [p->jvex ].firstedge==NULL ) graph->adjlist [p->jvex ].firstedge =p; else { q=graph->adjlist [p->jvex ].firstedge ; while(q!=NULL) { e=q; if(q->ivex ==p->ivex ) q=q->ilink ; else q=q->jlink ; } if(e->ivex ==p->ivex ) e->ilink =p; else e->jlink =p; } } } //设置访问标记 void SetMark(Graph *graph) { int i; for(i=1;i<=graph->vexnum ;i++) graph->adjlist [i].markV =0; } //深度遍历 void DFS(Graph *graph,int v) { EdgeNode *p; printf("%d ",v); graph->adjlist [v].markV =1; p=graph->adjlist [v].firstedge ; while(p!=NULL) { if(p->ivex ==v) { if(graph->adjlist [p->jvex ].markV ==0) { printf("<%d,%d>\n",p->ivex ,p->jvex ); DFS(graph,p->jvex ); } p=p->ilink ; } else { if(graph->adjlist [p->ivex].markV ==0) { printf("<%d,%d>\n",p->jvex ,p->ivex ); DFS(graph,p->ivex ); } p=p->jlink ; } } } //广度遍历 void BFS(Graph *graph,int u) { LinkQueue Q; EdgeNode *p; InitQueue(&Q); printf("%d ",u); graph->adjlist [u].markV =1; EnQueue(&Q,u); while(Q.front !=Q.rear ) { DeQueue(&Q,&u); p=graph->adjlist [u].firstedge ; while(p!=NULL) { if(p->ivex ==u) { if(graph->adjlist [p->jvex ].markV ==0) { EnQueue(&Q,p->jvex ); graph->adjlist [p->jvex ].markV =1; printf("<%d,%d>\n",p->ivex ,p->jvex ); printf("%d ",p->jvex ); } p=p->ilink ; } else { if(graph->adjlist [p->ivex ].markV ==0) { EnQueue(&Q,p->ivex ); graph->adjlist [p->ivex ].markV =1; printf("<%d,%d>\n",p->jvex ,p->ivex ); printf("%d ",p->ivex ); } p=p->jlink ; } } } } void main() { int u,v; Graph graph; char order; Initilized(&graph); CreateGraph(&graph); printf("输入命令（C/c：重新创建连通无向图 T/t深度遍历 广度遍历 E/e：结束）：\n"); scanf("%s",&order); while(order!='E'&&order!='e') { switch(order) { case 'C': case 'c': Initilized(&graph); CreateGraph(&graph); break; case 'T': case 't': printf("\n输入深度 广度遍历的起始点：\n"); scanf("%d",&v); u=v; while(v<=0||v>graph.vexnum ) { printf("\n输入顶点编号错误，请重新输入！"); scanf("%d",&v); u=v; } printf("\n深度遍历序列及相应的生成树:\n顶点序列： 生成树边集：\n"); SetMark(&graph); DFS(&graph,v); printf("\n广度遍历序列及相应生成树：\n顶点序列： 生成树边集：\n"); SetMark(&graph); BFS(&graph,u); break; } printf("\n输入命令（C：创建连通无向图 T/t：深度 广度遍历 E：结束）：\n"); scanf("%s",&order); } }