数据机构中关于图的变成习题.doc

标题:图的深度和广度优先遍历时限:2000ms内存限制:5000K总时限:3000ms描述:以邻接矩阵给出一张以整数编号为顶点的图,其中0表示不相连,1表示相连。按深度和广度优先进行遍历,输出全部结果。要求,遍历时优先较小的顶点。如,若顶点0与顶点2,顶点3,顶点4相连,:顶点个数邻接矩阵输出:DFS深度遍历输出WFS广度遍历输出输入样例:3011101110输出样例:DFS012102201WFS012102201提示:顶点整数从0开始来源:教材#include<iostream>#include<>#include<>#include<>usingnamespacestd;ode{intAdjVex;ode*NextArc;};typedefstructVNode{ode*FirstArc;}*AdjList;structUDG{intVexnum;AdjListVertices;};voidCreateUDG(UDG&G){scanf("%d",&);=(AdjList)calloc(,sizeof(VNode));inti,j;charch;ode*temp;for(i=0;i<;++i){[i].FirstArc=NULL;for(j=0;j<;++j){scanf("%c",&ch);if(ch=='1'){if([i].FirstArc){temp->NextArc=(ode*)malloc(sizeof(ode));temp=temp->NextArc;temp->AdjVex=j;}else{temp=[i].FirstArc=(ode*)malloc(sizeof(ode));temp->AdjVex=j;}}}if([i].FirstArc)temp->NextArc=NULL;}}voidDFS(AdjListVertices,inti,boolunvisited[]){unvisited[i]=false;printf("%d",i);ode*temp=Vertices[i].FirstArc;for(;temp;temp=temp->NextArc){i=temp->AdjVex;if(unvisited[i])DFS(Vertices,i,unvisited);}}voidDFSTraverse(UDGG){puts("DFS");boolunvisited[];inti;for(i=0;i<;++i){memset(unvisited,true,*sizeof(bool));DFS(,i,unvisited);putchar('\n');}}structQElemType{intVex;};typedefstructQNode{QElemTypeData;QNode*Next;}*QueuePtr;structQueue{QueuePtrFront,Rear;};voidInitQueue(Queue&Q){==(QueuePtr)malloc(sizeof(QNode));->Next=NULL;}voidEnQueue(Queue&Q,QElemTypedata){->Next=(QueuePtr)malloc(sizeof(QNode));=->Next;->Data=data;->Next=NULL;}boolDeQueue(Queue&Q,QElemType&data){if(==)returnfalse;QueuePtrtemp=;=temp->Next;free(temp);data=->Data;returntrue;}voidDestroyQueue(QueueQ){while(){=->Next;free();=;}}voidBFSTraverse(UDGG){puts("WFS");boolunvisited[];intstart,i;ode*temp;QElemTypedata;QueueQ;InitQueue(Q);for(start=0;start<;++start){memset(unvisited