数据结构_图遍历的演示

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

2、ct 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;/图的边数

3、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* Graph

4、Traverse:DFSForest(int v)int i,j;TNode *p,*q,*DT;j=v;for(i=0;i<vertexNumberber;i+)Visitedi=0;for(i=0;i<vertexNumberber;i+)if(Visited(i+j)%vertexNumberber=0)p=new TNode;p->data=VexList(i+j)%vertexNumberber.vertex;p->fristchild=NULL;p->nextchild=NULL;DT=p;q=p;DFSTree(i+j)%vertexNumberbe

5、r),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-&g

6、t;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;i<vertexNumberber;i+)Visitedi=0;for(i=0;i<vertexNumberber;i+)if(Visited(i+j)%vertexNumberber=0)p=new TNode;p->data=VexList(i+j)%vert

7、exNumberber.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;w

8、hile(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) 打印函

9、数：按照凹入表方式打印树。void GraphTraverse:PrintTree(TNode *T,int i)int j;TNode *p;cout<<ends;for(j=1;j<=i;j+)cout<<ends<<ends;cout<<T->data<<endl;for(p=T->fristchild;p;p=p->nextchild)PrintTree(p,i+1);2. 主函数的实现：void main()string s1;int flag;TNode *DT,*BT;GraphTraverse

10、graphnet;string begin;int i;flag=atoi(s1.c_str(); while(flag>5|flag<1)cout<<"输入错误，请重新输入！"<<endl;cout<<endl<<"请输入操作序号："cin>>s1;flag=atoi(s1.c_str(); while(flag!=5)switch(flag)case 1:graphnet.ReadFile();break;case 2:graphnet.DisplayGraph();break;

11、case 3:cout<<"请输入遍历起点："cin>>begin;for(i=0;i<graphnet.vertexNumberber;i+)if(graphnet.VexListi.vertex=begin)break;if(i=graphnet.vertexNumberber)cout<<"输入的起点不存在！"<<endl;break;elseDT=graphnet.DFSForest(i);cout<<"深度优先遍历结果如下（凹入表）："<<endl

12、;graphnet.PrintTree(DT,0);break;case 4:cout<<"请输入遍历起点："cin>>begin;for(i=0;i<graphnet.vertexNumberber;i+)if(graphnet.VexListi.vertex=begin)break;if(i=graphnet.vertexNumberber)cout<<"输入的起点不存在！"<<endl;break;elseBT=graphnet.BFSForest(i);cout<<"广度

13、优先遍历结果如下（凹入表）："<<endl;graphnet.PrintTree(BT,0);break;flag=atoi(s1.c_str(); while(flag>5|flag<1)cout<<"输入错误，请重新输入！"<<endl;cout<<endl<<"请输入操作序号："cin>>s1;flag=atoi(s1.c_str(); 四、 用户手册1. 本程序的执行文件为：GraphTraverse.exe2. 进入程序的用户界面，并根据程序提示，输入文件名及其路径，读取文件