资源描述:
《图遍历的演示实习报告.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、图遍历的演示题目:试设计一个程序,演示在连通和非连通的无向图上访问全部结点的操作班级:07级计科院网络工程姓名:刘振帮学号:07066017完成日期:一、需求分析1、以邻接多重表为存储结构;2、实现连通和非连通的无向图的深度优先和广度优先遍历;3、要求利用栈实现无向图的广度和深度优先遍历;4、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和生成树的边集;5、用凹入表打印生成树;6、求出从一个结点到另外一个结点,但不经过另外一个指定结点的所有简单路径;6、本程序用C++语言编写,在TURBOC++3.0环境下通过。二、概要设计1、设定图的抽象数据类型:ADTGraph{
2、数据对象V:V是具有相同特性的数据元素的集合,称为点集.数据关系R:R={VR}VR={(v,w>
3、v,w属于V,(v,w>表示v和w之间存在的路径}基本操作P:CreatGraph(&G,V,VR>初始条件:V是图的顶点集,VR是图中弧的集合.操作结果:按V和VR是定义构造图G.DestroyGraph(&G>初始条件:图G存在操作结果:销毁图GLocateVex(G,u>初始条件:图G存在,u和G中顶点有相同的特征操作结果:若图G中存在顶点u,则返回该顶点在图中的位置。否则返回其他信息GetVex(G,v>初始条件:图G存在,v是G中顶点操作结果:返回v的值FirstAjv
4、ex(G,v>初始条件:图G存在,v是G中顶点操作结果:返回v的第一个邻接顶点,若顶在图中没有邻接顶点,则返回为空NextAjvex(G,v,w>初始条件:图G存在,v是G中顶点,w是v的邻接顶点操作结果:返回v的下一个邻接顶点,若w是v的最后一个邻接顶点,则返回空DeleteVexx(&G,v>初始条件:图G存在,v是G中顶点操作结果:删除顶点v已经其相关的弧DFSTraverse(G,visit(>>初始条件:图G存在,visit的顶点的应用函数操作结果:16/16对图进行深度优先遍历,在遍历过程中对每个结点调用visit函数一次,一旦visit失败,则操作失败b5E2RG
5、bCAPBFSTraverse(G,visit(>>初始条件:图G存在,visit的顶点的应用函数操作结果:对图进行广度优先遍历,在遍历过程中对每个结点调用visit函数一次,一旦visit失败,则操作失败p1EanqFDPw}ADTGraph2、设定栈的抽象数据类型:ADTStack{数据对象:D={ai
6、ai∈CharSet,i=1,2,……,n,n≥0}数据关系:R1={
7、ai-1,ai∈D,i=2,……,n}基本操作:InitStack(&S>操作结果:构造一个空栈S。DestroyStack(&S>初始条件:栈S已存在。操作结果:栈S被销毁。Push
8、(&S,e>。初始条件:栈S已存在。操作结果:在栈S的栈顶插入新的栈顶元素e。Pop(&S,e>。初始条件:栈S已存在。操作结果:删除S的栈顶元素,并以e返回其值。StackEmpty(S>初始条件:栈S已存在。操作结果:若S为空栈,则返回TRUE,否则返回FALSE。}ADTStack3、设定队列的抽象数据类型:ADTQueue{数据对象:D={ai
9、ai属于Elemset,i=1,2….,n,n>=0}数据关系:R1={
10、ai-1,ai属于D,i=1,2,…,n}约定ai为端为队列头,an为队列尾基本操作:InitQueue(&Q>操作结果:构造一个空队列
11、QDestryoQueue(&Q>初始条件:队列Q已存在。操作结果:队列Q被销毁,不再存在。EnQueue(&Q,e>初始条件:队列Q已经存在操作结果:插入元素e为Q的新的队尾元素DeQueue(&Q,&E>初始条件:Q为非空队列操作结果:删除Q的队尾元素,并用e返回其值QueueEmpty(Q>初始条件:队列已经存在操作结果:若队列为空,则返回TRUE,否则返回FLASE16/16}ADTQueue4、本程序包含九个模块:1)主程序模块voidmain(>{手动构造一个图;从文件导入一个图;显示图的信息;进行深度优先遍历图;进行广度优先遍历图;保存图到一个文件;寻找路径;销毁
12、一个图;};2)手动构造一个图-自己输入图的顶点和边生成一个图;3)从文件导入一个图;4)显示图的信息-打印图的所有顶点和边;5)进行深度优先遍历图-打出遍历的结点序列和边集;6)进行广度优先遍历图-打出遍历的结点序列和边集;7)保存图到一个文件;8)寻找从起点到终点,但中间不经过某点的所有简单路径;9)销毁图。三、详细设计10)顶点,边和图类型#defineMAX_INFO10/*相关信息字符串的最大长度+1*/#defineMAX_VERTEX_NUM20/*图中顶点数的最大值*/typ