图的遍历（有向图和无向图）

#include"adjlist.h" void DFTraverse(AdjlistG buffer,int start){ Bool *vmark=NULL; int *sequence=NULL; int i=0,j=0; EdgeQue treeedgeque; Edge *buf=NULL; if(!(sequence=(int*)malloc(sizeof(int)*buffer.vexNum))) { printf("内存不足！遍历失败！\n"); system("pause"); return; } if(!(vmark=(Bool*)malloc(sizeof(Bool)*buffer.vexNum))) { printf("内存不足！遍历失败！\n"); system("pause"); return; } for(i=0;i<buffer.vexNum;i++) vmark[i]=False; initialQue(&treeedgeque); if(!DFSUG(buffer,start,vmark,sequence,&treeedgeque)) return; for(i=0;i<buffer.vexNum;i++){ if(!vmark[i]){ if(j==0) printf("输入的%s向图不是连通图！\n",buffer.kind==UG?"无":"有"),j++; if(!DFSUG(buffer,i+1,vmark,sequence,&treeedgeque)) return ; } } printf("该图（邻接表表示）结点的深度优先遍历顺序为："); for(i=0;i<buffer.vexNum;i++) printf(" %d",sequence[i]); printf("\n该图（邻接表表示）的深度优先遍历的生成树的边集为：\n"); i=0; while(!isempty(&treeedgeque)){ if(buf=deEdgeQue(&treeedgeque)){ printf("(%d, %d)\t",buf->edgebegin,buf->edgeend); i++; if(i%6!=0) continue; printf("\n"); i=0; } else break; } return; } Bool DFSUG(AdjlistG buffer,int start,Bool vmark[],int sequence[],EdgeQue *treeedgeque){ static int count=0; Edge buf; Arc *p=NULL; if(!isinit(treeedgeque)){ printf("队列（有向边）未初始化，遍历失败！\n"); return False; } vmark[start-1]=True; sequence[count++]=start; for(p=buffer.list[start-1].firstAdjArc;p;p=p->nextAdjArc){ if(!vmark[p->vex-1]){ buf.edgebegin=start; buf.edgeend=p->vex; enEdgeQue(treeedgeque,buf); DFSUG(buffer,p->vex,vmark,sequence,treeedgeque); } } if(count==buffer.vexNum) count=0; return True; } void BFTraverse(AdjlistG buffer,int start){ Bool *vmark=NULL; EdgeQue treeedgeque; Edge *buf=NULL; int *sequence=NULL; int i=0,j=0; int nextin=0; int nextout=0; if(!(sequence=(int*)malloc(sizeof(int)*buffer.vexNum))) { printf("内存不足！遍历失败！\n"); system("pause"); return; } if(!(vmark=(Bool*)malloc(sizeof(Bool)*buffer.vexNum))) { printf("内存不足！遍历失败！\n"); system("pause"); return; } for(i=0;i<buffer.vexNum;i++) vmark[i]=False; initialQue(&treeedgeque); nextout=nextin=BFSUG(buffer,start,vmark,sequence,&treeedgeque,nextin,nextout); if(nextin==-1) return; for(i=0;i<buffer.vexNum;i++){ if(!vmark[i]){ if(j==0) printf("输入的%s向图不是连通图！\n",buffer.kind==UG?"无":"有"),j++; nextout=nextin=BFSUG(buffer,i+1,vmark,sequence,&treeedgeque,nextin,nextout); if(nextin==-1) return; } } printf("该图（邻接表表示）结点的宽度优先遍历顺序为："); for(i=0;i<buffer.vexNum;i++) printf(" %d",sequence[i]); printf("\n该图（邻接表表示）的宽度优先遍历的生成树的边集为：\n"); i=0; while(!isempty(&treeedgeque)){ if(buf=deEdgeQue(&treeedgeque)){ printf("(%d, %d)\t",buf->edgebegin,buf->edgeend); i++; if(i%6!=0) continue; printf("\n"); i=0; } else break; } return; } int BFSUG(AdjlistG buffer,int start,Bool vmark[],int sequence[],EdgeQue *treeedgeque,int nextin,int nextout){ int i=0; Arc *p=NULL; Edge buf; if(!isinit(treeedgeque)){ printf("队列（有向边）未初始化，遍历失败！\n"); return -1; } sequence[nextin++]=start; vmark[start-1]=True; while(nextin!=nextout){ i=sequence[nextout++]; p=buffer.list[i-1].firstAdjArc; while(p){ if(!vmark[p->vex-1]){ sequence[nextin++]=p->vex; vmark[p->vex-1]=True; buf.edgebegin=i; buf.edgeend=p->vex; enEdgeQue(treeedgeque,buf); } p=p->nextAdjArc; } } return nextin; } void DFNRTraverse(AdjlistG buffer,int start){ Bool *vmark=NULL; int *sequence=NULL; int i=0,j=0; EdgeQue treeedgeque; Edge *buf=NULL; VexStack stack; if(!(sequence=(int*)malloc(sizeof(int)*buffer.vexNum))) { printf("内存不足！遍历失败！\n"); system("pause"); return; } if(!(vmark=(Bool*)malloc(sizeof(Bool)*buffer.vexNum))) { printf("内存不足！遍历失败！\n"); system("pause"); return; } for(i=0;i<buffer.vexNum;i++) vmark[i]=False; initialQue(&treeedgeque); initialStack(&stack,buffer.vexNum); if(!DFNRSUG(buffer,start,vmark,sequence,&treeedgeque,&stack)) return ; for(i=0;i<buffer.vexNum;i++){ if(!vmark[i]){ if(j==0) printf("输入的%s向图不是连通图！\n",buffer.kind==UG?"无":"有"),j++; if(!DFNRSUG(buffer,i+1,vmark,sequence,&treeedgeque,&stack)) return ; } } printf("该图（邻接表表示）结点的非递归深度优先遍历顺序为："); for(i=0;i<buffer.vexNum;i++) printf(" %d",sequence[i]); printf("\n该图（邻接表表示）的非递归深度优先遍历的生成树的边集为：\n"); i=0; while(!isempty(&treeedgeque)){ if(buf=deEdgeQue(&treeedgeque)){ printf("(%d, %d)\t",buf->edgebegin,buf->edgeend); i++; if(i%6!=0) continue; printf("\n"); i=0; } else break; } return; } Bool DFNRSUG(AdjlistG buffer,int start,Bool vmark[],int sequence[],EdgeQue *treeedgeque,VexStack *stack){ static int count=0; int nextpos; Arc *p; Edge buf; if(!isinit(treeedgeque)||!isinitS(stack)){ printf("队列（有向边）或栈（图结点）未初始化，遍历失败！\n"); return False; } push(stack,start); vmark[start-1]=True; sequence[count++]=start; while(!isemptyS(stack)){ nextpos=pop(stack); p=buffer.list[nextpos-1].firstAdjArc; while(p){ if(!vmark[p->vex-1]){ vmark[p->vex-1]=True; sequence[count++]=p->vex; buf.edgebegin=nextpos; buf.edgeend=p->vex; enEdgeQue(treeedgeque,buf); break; } p=p->nextAdjArc; } if(p){ push(stack,nextpos); push(stack,p->vex); } } if(count==buffer.vexNum) count=0; return True; }