题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已经其相关的弧
DFSTraver(G,visit())
初始条件: 图G存在,visit的顶点的应用函数
操作结果: 对图进行深度优先遍历,在遍历过程中对每个结点调用visit函数一次,一旦visit失败,则操作失败
BFSTraver(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返回其值。
apple序列号StackEmpty(S)
初始条件：栈S已存在。
操作结果：若S为空栈，则返回TRUE，否则返回FALSE。
}ADT窃读记课文原文 Stack
3、设定队列的抽象数据类型：
ADT Queue{
数据对象:D={ai|ai属于Elemt,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、本程序包含九个模块：
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{
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中删除边<v,w>。
Status DeleteVex(AMLGraph &G,VertexType v)；
//在G中删除顶点v及其相关的边。
void DestroyGraph(AMLGraph &G)；
//销毁一个图
void Display(AMLGraph G)；
//输出无向图的邻接多重表G。
血压偏高怎么调理void DFSTraver(AMLGraph G,VertexType start,int(*visit)(VertexType))；
//从start顶点起,（利用栈非递归）深度优先遍历图G。
void BFSTraver(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<G.edgenum;++k) /* 构造表结点链表 */
`{
读入两个顶点va、vb；
i=LocateVex(G,va); /* 一端 */
j=LocateVex(G,vb); /* 另一端 */
p=(EBox*)malloc(szeof(EBox));
p->mark=unvisited; /* 设初值 */耍 p->ivex=i;
p->jvex=j;
p࠭>info=NULL;M p->ilink=G.adjmulist[i].firstedge; /* 插在表头 */
G.adjmulist[i].firstedge=p;
p->jlink=G.adjmulist[j].firstedge; /* 插在表头 */
G.adjmulist[j].firstedge=p;
}
}
void Display(AMLGraph G)
{ /* 输出无向图的邻接多重表G */
MarkUnvizited(G); 百家讲坛李煜
输出无向图的所有顶点；
for(i=0;i<G.vexnum;i++)
{
p=G.adjmulist[i].firstedge;
while(p)
if(p->ivex==i) /* 边的i端与该顶点有关 */
