文档介绍:题目:图遍历的演示编译环境:MicrosoftVisualStudio2010功能实现:以邻接表为存储结构,演示在连通无向图上访问全部节点的操作; 实现连通无向图的深度优先遍历和广度优先遍历;建立深度优先生成树和广度优先生成树,按凹入表或树形打印生成树。需求分析以邻接表为存储结构,演示在连通无向图上访问全部节点的操作。该无向图为一个交通网络,共25个节点,30条边,遍历时需要以用户指定的节点为起点,建立深度优先生成树和广度优先生成树,再按凹入表或树形打印生成树。程序的测试数据:。概要设计主要数据结构设计:ode //边表结点{ intvexIndex; //邻接点域,即邻接点在顶点表中的下标 ode*next; };structVertexNode //顶点表结点{ stringvertex; //数据域 ode*firstArc;};structTNode //树结点{ stringdata; structTNode*fristchild,*nextchild;};邻接表类设计:classGraphTraverse{public: VertexNodeVexList[MaxSize]; //顶点表数组 intvertexNumberber; //图的顶点数 umberber; //图的边数 boolHasCreated; //图是否创建 voidReadFile(); //从文件读取数据,并建立该图 voidDisplayGraph(); //以邻接表显示图 TNode*DFSForest(int); //建立深度优先生成树 voidDFSTree(int,TNode*); //深度优先遍历图 TNode*BFSForest(int); //建立广度优先生成树 voidBFSTree(int,TNode*); //广度优先遍历图 voidPrintTree(TNode*,int); //按照凹入表方式打印树};详细设计主要操作函数的实现:建立深度优先生成树函数:TNode*GraphTraverse::DFSForest(intv){ inti,j; TNode*p,*q,*DT; j=v; for(i=0;i<vertexNumberber;i++) { Visited[i]=0; } for(i=0;i<vertexNumberber;i++) { if(Visited[(i+j)%vertexNumberber]==0) { p=newTNode; p->data=VexList[(i+j)%vertexNumberber].vertex; p->fristchild=NULL; p->nextchild=NULL; DT=p; q=p; DFSTree(((i+j)%vertexNumberber),p); } } returnDT;}深度优先遍历图函数:voidGraphTraverse::DFSTree(intv,TNode*DT){ intj=0; inti=0; TNode*p,*q; intfirst=1; Visited[v]=1; for(ode*m=VexList[v].firstArc;m;m=m->next) { j=m->vexIndex; if(Visited[j]==0) { p=newTNode; p->data=VexList[j].vertex; p->fristchild=NULL; p->nextchild=NULL; if(first) { DT->fristchild=p; first=0; } else q->nextchild=p; q=p; DFSTree(j,q); } }}建立广度优先生成树函数:TNode*GraphTraverse::BFSForest(intv){ inti,j; TNode*p,*q,*BT; BT=NULL; j=v; for(i=0;i<vertexNumberber;i++) { Visited[i]=0; } for(i=0;i<vertexNumberber;i++) { if(Visited[(i+j)%vertexNumberber]==0) { p=newTNode; p->data=VexList[(i+j)%vertexNumberber].vertex; p->fristchild=NULL; p->nextchild=NULL; BT=p; q=p; BFSTree(((i+j)%vertexNumberber),p); } } returnBT;}广度优先遍历图函数:voidGraphTraverse::BFSTree(intv,TNode*BT){ intfront=-1; i