图遍历的演示实习报告.doc

图遍历的演示
题目:试设计一个程序,演示在连通和非连通的无向图上访问全部结点的操作
班级:07级计科院网络工程姓名:刘振帮学号:07066017 完成日期:
一、需求分析
1、以邻接多重表为存储结构;
2、实现连通和非连通的无向图的深度优先和广度优先遍历;
3、要求利用栈实现无向图的广度和深度优先遍历;
4、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和生成树的边集;
5、用凹入表打印生成树;
6、求出从一个结点到另外一个结点,但不经过另外一个指定结点的所有简单路径;
6、本程序用C++语言编写,在TURBO C++ 。
二、概要设计
1、设定图的抽象数据类型:
ADT Graph{
数据对象V:V是具有相同特性的数据元素的集合,称为点集.
数据关系R:
R={VR}
VR={(v,w)|v,w属于V,(v,w)表示v和w之间存在的路径}
基本操作P:
CreatGraph(&G,V,VR)
初始条件:V是图的顶点集,VR是图中弧的集合.
操作结果:按V和VR是定义构造图G.
DestroyGraph(&G)
初始条件:图G存在
操作结果:销毁图G
LocateVex(G,u)
初始条件: 图G存在,u和G中顶点有相同的特征
操作结果:若图G中存在顶点u,则返回该顶点在图中的位置;否则返回其他信息
GetVex(G,v)
初始条件: 图G存在,v是G中顶点
操作结果:返回v的值
FirstAjvex(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的顶点的应用函数
操作结果: 对图进行深度优先遍历,在遍历过程中对每个结点调用visit函数一次,一旦visit失败,则操作失败
BFSTraverse(G,visit())
初始条件: 图G存在,visit的顶点的应用函数
操作结果:对图进行广度优先遍历,在遍历过程中对每个结点调用visit函数一次,一旦visit失败,则操作失败
}ADT Graph
2、设定栈的抽象数据类型:
ADT Stack{
数据对象:D={ai | ai∈CharSet,i=1,2,……,n,n≥0}
数据关系:R1={<ai-1,ai> | ai-1,ai∈D,i=2,……,n}
基本操作:
InitStack(&S)
操作结果:构造一个空栈S。
DestroyStack(&S)
初始条件:栈S已存在。
操作结果:栈S被销毁。
Push(&S,e);
初始条件:栈S已存在。
操作结果:在栈S的栈顶插入新的栈顶元素e。
Pop(&S,e);
初始条件:栈S已存在。
操作结果:删除S的栈顶元素,并以e返回其值。
StackEmpty(S)
初始条件:栈S已存在。
操作结果:若S为空栈,则返回TRUE,否则返回FALSE。
}ADT Stack
3、设定队列的抽象数据类型:
ADT Queue{
数据对象:D={ai|ai属于Elemset,i=1,2….,n,n>=0}
数据关系:R1={<ai-1,ai>|ai-1,ai属于D,i=1,2,…,n}
约定ai为端为队列头,an为队列尾
基本操作:
InitQueue(&Q)
操作结果:构造一个空队列Q
DestryoQueue(&Q)
初始条件:队列Q已存在。
操作结果:队列Q被销毁,不再存在。
EnQueue(&Q,e)
初始条件:队列Q已经存在
操作结果:插入元素e为Q的新的队尾元素
DeQueue(&Q,&E)
初始条件:Q为非空队列
操作结果:删除Q的队尾元素,并用e返回其值
QueueEmpty(Q)
初始条件:队列已经存在
操作结果:若队列为空,则返回TRUE,否则返回FLASE
}ADT Queue
4、本程序包含九个模块:
主程序模块
void main ()
{
手动构造一个图;
从文件导入一个图;
显示图的信息;
进行深度优先遍历图;
进行广度优先遍历图;
保存图到一个文件;
寻找路径;
销毁一个图;
};
手动构造一个图-自己输入图的顶点和边生成一个图;
从文件导入一个图;
显示图的信息