发布时间 : 星期日 文章图遍历的演示报告及源代码更新完毕开始阅读
计算机软件技术基础课程设计 图的遍历的演示 龚陈继
题5.3 图遍历的演示
实习报告
题目:试设计一个程序,演示在连通的无向图上访问全部结点的操作
一、需求分析
1、以邻接多重表为存储结构；
2、实现连通和非连通的无向图的深度优先和广度优先遍历； 3、要求利用栈实现无向图的深度优先遍历；
4、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和生成树的边集； 5、用凹入表打印生成树；
6、求出从一个结点到另外一个结点，但不经过另外一个指定结点的所有简单路径； 6、本程序用C++语言编写，在Visial C++ 6.0环境下通过。
二、概要设计
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的顶点的应用函数
Page 1 of 18
计算机软件技术基础课程设计 图的遍历的演示 龚陈继
操作结果: 对图进行深度优先遍历,在遍历过程中对每个结点调用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={
操作结果：构造一个空栈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为端为队列头,an为队列尾
基本操作:
InitQueue(&Q)
操作结果:构造一个空队列Q
DestryoQueue(&Q)
初始条件：队列Q已存在。
操作结果：队列Q被销毁，不再存在。
EnQueue(&Q,e)
初始条件:队列Q已经存在
操作结果:插入元素e为Q的新的队尾元素 DeQueue(&Q,&E)
初始条件:Q为非空队列
操作结果:删除Q的队尾元素,并用e返回其值 QueueEmpty(Q)
Page 2 of 18
计算机软件技术基础课程设计 图的遍历的演示 龚陈继
初始条件:队列已经存在
操作结果:若队列为空,则返回TRUE,否则返回FLASE
}ADT Queue
4、本程序包含九个模块： 1）主程序模块 void main () {
手动构造一个图； 从文件导入一个图； 显示图的信息；
进行深度优先遍历图； 进行广度优先遍历图； 保存图到一个文件； 寻找路径； 销毁一个图； }；
2）手动构造一个图-自己输入图的顶点和边生成一个图； 3）从文件导入一个图；
4）显示图的信息-打印图的所有顶点和边；
5）进行深度优先遍历图-打出遍历的结点序列和边集； 6）进行广度优先遍历图-打出遍历的结点序列和边集； 7）保存图到一个文件；
8）寻找从起点到终点，但中间不经过某点的所有简单路径； 9）销毁图。
三、详细设计
1、顶点,边和图类型
#define MAX_INFO 10 /* 相关信息字符串的最大长度+1 */ #define MAX_VERTEX_NUM 20 /* 图中顶点数的最大值*/
typedef char InfoType; /*相关信息类型*/ typedef char VertexType; /* 字符类型 */ typedef enum{unvisited,visited}VisitIf;
typedef struct EBox{
VisitIf mark; /* 访问标记 */
int ivex,jvex; /* 该边依附的两个顶点的位置 */
struct EBox *ilink,*jlink; /* 分别指向依附这两个顶点的下一条边 */ InfoType *info; /* 该边信息指针 */ }EBox;
typedef struct{ VertexType data;
EBox *firstedge; /* 指向第一条依附该顶点的边 */ }VexBox;
typedef struct{
Page 3 of 18
计算机软件技术基础课程设计 图的遍历的演示 龚陈继
VexBox adjmulist[MAX_VERTEX_NUM];
int vexnum,edgenum; /* 无向图的当前顶点数和边数 */ }AMLGraph;
图的基本操作如下：
int LocateVex(AMLGraph G,VertexType u)；
// 查G和u有相同特征的顶点，若存在则返回该顶点在无向图中位置;否则返回-1。 VertexType& GetVex(AMLGraph G,int v)； //以v返回邻接多重表中序号为i的顶点。 int FirstAdjVex(AMLGraph G,VertexType v)；
//返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1。 int NextAdjVex(AMLGraph G,VertexType v,VertexType w)；
//返回v的(相对于w的)下一个邻接顶点的序号若w是v的最后一个邻接点,则返回-1。 void CreateGraph(AMLGraph &G)；
//采用邻接多重表存储结构,构造无向图G。
Status DeleteArc(AMLGraph &G,VertexType v,VertexType w)； //在G中删除边
Status DeleteVex(AMLGraph &G,VertexType v)； //在G中删除顶点v及其相关的边。 void DestroyGraph(AMLGraph &G)； //销毁一个图
void Display(AMLGraph G)； //输出无向图的邻接多重表G。
void DFSTraverse(AMLGraph G,VertexType start,int(*visit)(VertexType))； //从start顶点起,（利用栈非递归）深度优先遍历图G。
void BFSTraverse(AMLGraph G,VertexType start,int(*Visit)(VertexType))； //从start顶点起,广度优先遍历图G。 void MarkUnvizited(AMLGraph G)； //置边的访问标记为未被访问。
其中部分操作的伪码算法如下：
void CreateGraph(AMLGraph &G)
{ /* 采用邻接多重表存储结构,构造无向图G */ DestroyGraph(G); /*如果图不空,先销毁它*/ 输入无向图的顶点数G.vexnum； 输入无向图的边数G.edgenum； 输入顶点的信息IncInfo； 依次输入无向图的所有顶点；
for(k=0;k 读入两个顶点va、vb； i=LocateVex(G,va); /* 一端 */ j=LocateVex(G,vb); /* 另一端 */ p=(EBox*)malloc(s?zeof(EBox)); Page 4 of 18