数据结构_图遍历的演示

《数据结构_图遍历的演示》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实习报告题目：图遍历的演示编译环境：MicrosoftVisualStudio2010功能实现：以邻接表为存储结构，演示在连通无向图上访问全部节点的操作；实现连通无向图的深度优先遍历和广度优先遍历；建立深度优先生成树和广度优先生成树，按凹入表或树形打印生成树。一、需求分析1.以邻接表为存储结构，演示在连通无向图上访问全部节点的操作。该无向图为一个交通网络，共25个节点，30条边，遍历时需要以用户指定的节点为起点，建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。2.程序的测试数据：graph.tx

2、t文件所表示的无向交通图。二、概要设计1.主要数据结构设计：structArcNode//边表结点{intvexIndex;//邻接点域，即邻接点在顶点表中的下标ArcNode*next;};structVertexNode//顶点表结点{stringvertex;//数据域ArcNode*firstArc;};structTNode//树结点{stringdata;structTNode*fristchild,*nextchild;};2.邻接表类设计：classGraphTraverse{public:Ve

3、rtexNodeVexList[MaxSize];//顶点表数组intvertexNumberber;//图的顶点数intarcNumberber;//图的边数boolHasCreated;//图是否创建voidReadFile();//从文件读取数据，并建立该图voidDisplayGraph();//以邻接表显示图TNode*DFSForest(int);//建立深度优先生成树voidDFSTree(int,TNode*);//深度优先遍历图TNode*BFSForest(int);//建立广度优先生成树v

4、oidBFSTree(int,TNode*);//广度优先遍历图voidPrintTree(TNode*,int);//按照凹入表方式打印树};一、详细设计1.主要操作函数的实现：(1)建立深度优先生成树函数：TNode*GraphTraverse::DFSForest(intv){inti,j;TNode*p,*q,*DT;j=v;for(i=0;i

5、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;}(2)深度优先遍历图函数：voidGraphTraverse::DFSTree(intv,TNode*DT){intj=0;inti=0;TNode*p,*q;intf

6、irst=1;Visited[v]=1;for(ArcNode*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;}elseq->nextchild=p;q=p;DFSTree(j,q);}}}(1)建立广度优先生

7、成树函数：TNode*GraphTraverse::BFSForest(intv){inti,j;TNode*p,*q,*BT;BT=NULL;j=v;for(i=0;idata=VexList[(i+j)%vertexNumberber].vertex;p->fristchi

8、ld=NULL;p->nextchild=NULL;BT=p;q=p;BFSTree(((i+j)%vertexNumberber),p);}}returnBT;}(1)广度优先遍历图函数：voidGraphTraverse::BFSTree(intv,TNode*BT){intfront=-1;intrear=-1;intj=0;inta,b;intfirst=1;a=b=0;TNo