数据结构_图遍历的演示.doc

实习报告题目：图遍历的演示编译环境：Microsoft Visual Studio 2010功能实现：以邻接表为存储结构，演示在连通无向图上访问全部节点的操作；实现连通无向图的深度优先遍历和广度优先遍历；建立深度优先生成树和广度优先生成树，按凹入表或树形打印生成树。一、 需求分析1. 以邻接表为存储结构，演示在连通无向图上访问全部节点的操作。该无向图为一个交通网络，共25个节点，30条边，遍历时需要以用户指定的节点为起点，建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。2. 程序的测试数据：graph.txt文件所表示的无向交通图。二、 概要设计1. 主要数据结构设计：struct ArcNode/边表结点int vexIndex;/邻接点域，即邻接点在顶点表中的下标ArcNode* next;struct VertexNode/顶点表结点string vertex;/数据域ArcNode* firstArc;struct TNode/树结点string data;struct TNode *fristchild, *nextchild;2. 邻接表类设计：class GraphTraversepublic:VertexNode VexListMaxSize;/顶点表数组int vertexNumberber;/图的顶点数int arcNumberber;/图的边数bool HasCreated;/图是否创建void ReadFile();/从文件读取数据，并建立该图void DisplayGraph();/以邻接表显示图TNode* DFSForest(int);/建立深度优先生成树void DFSTree(int, TNode*);/深度优先遍历图TNode* BFSForest(int);/建立广度优先生成树void BFSTree(int, TNode*);/广度优先遍历图void PrintTree(TNode*, int);/按照凹入表方式打印树;三、 详细设计1. 主要操作函数的实现：(1) 建立深度优先生成树函数：TNode* GraphTraverse:DFSForest(int v)int i,j;TNode *p,*q,*DT;j=v;for(i=0;ivertexNumberber;i+)Visitedi=0;for(i=0;idata=VexList(i+j)%vertexNumberber.vertex;p-fristchild=NULL;p-nextchild=NULL;DT=p;q=p;DFSTree(i+j)%vertexNumberber),p);return DT;(2) 深度优先遍历图函数：void GraphTraverse:DFSTree(int v, TNode* DT)int j=0;int i=0;TNode *p,*q;int first=1;Visitedv=1;for(ArcNode *m=VexListv.firstArc;m;m=m-next)j=m-vexIndex;if(Visitedj=0)p=new TNode;p-data=VexListj.vertex;p-fristchild=NULL;p-nextchild=NULL;if(first)DT-fristchild=p;first=0;elseq-nextchild=p;q=p;DFSTree(j,q);(3) 建立广度优先生成树函数：TNode* GraphTraverse:BFSForest(int v)int i,j;TNode *p,*q,*BT;BT=NULL;j=v;for(i=0;ivertexNumberber;i+)Visitedi=0;for(i=0;idata=VexList(i+j)%vertexNumberber.vertex;p-fristchild=NULL;p-nextchild=NULL;BT=p;q=p;BFSTree(i+j)%vertexNumberber),p);return BT;(4) 广度优先遍历图函数：void GraphTraverse:BFSTree(int v,TNode*BT)int front=-1;int rear=-1;int j=0;int a,b;int first=1;a=b=0;TNode *m, *n, *r, *curMaxSize;r=BT;ArcNode *p;Visitedv=1;Query+rear=v;while(front!=rear)first=1;v=Query+front;for(p=VexListv.firstArc;p;p=p-next)j=p-vexIndex;if(Visitedj=0)m=new TNode;m-data=VexListj.vertex;m-fristchild=NULL;m-nextchild=NULL;Visitedj=1;Query+rear=j;if(first)r-fristchild=m;first=0;elsen-nextchild=m;cura+=m;n=m;r=curb+;(5) 打印函数：按照凹入表方式打印树。void GraphTraverse:PrintTree(TNode *T,int i)int j;TNode *p;coutends;for(j=1;j=i;j+)coutendsends;coutdatafristchild;p;p=p-nextchild)PrintTree(p,i+1);2. 主函数的实现：void main()string s1;int flag;TNode *DT,*BT;GraphTraverse graphnet;string begin;int i;flag=atoi(s1.c_str(); while(flag5|flag1)cout输入错误，请重新输入！endl;coutendls1;flag=atoi(s1.c_str(); while(flag!=5)switch(flag)case 1:graphnet.ReadFile();break;case 2:graphnet.DisplayGraph();break;case 3:coutbegin;for(i=0;igraphnet.vertexNumberber;i+)if(graphnet.VexListi.vertex=begin)break;if(i=graphnet.vertexNumberber)cout输入的起点不存在！endl;break;elseDT=graphnet.DFSForest(i);cout深度优先遍历结果如下（凹入表）：endl;graphnet.PrintTree(DT,0);break;case 4:coutbegin;for(i=0;igraphnet.vertexNumberber;i+)if(graphnet.VexListi.vertex=begin)break;if(i=graphnet.vertexNumberber)cout输入的起点不存在！endl;break;elseBT=graphnet.BFSForest(i);cout广度优先遍历结果如下（凹入表）：5|flag1)cout输入错误，请重新输入！endl;coutendls1;flag=atoi(s1.c_str(); 四、 用户手册1. 本程序的执行文件为：GraphTraverse.exe2. 进入程序的用户界面，并根据程序提示，输入文件名及其路径，读取文件中的数据：3. 显示当前图：4. 输入遍历起点，进行深度优先遍历（或者广