-
实现图的遍历算法
1
．
需求分析
对于下图
< br>G
，
编写一个程序输出从顶点
0
开始的深度优先遍历序列
（非递归算法）
和广度优
先遍历序列（非递归算法）
。
2
．
系统设计
1
．用到的抽象数据类型的定义
图的抽象数据类型定义：
ADT
Graph{
数据对象
V
：
V
是具有相同
特性的数据元素的集合，称为顶点集
数据关系
R
：
R={VR}
VR={
∈
V
且
P(v,w
),
表示从
v
到
w
的弧，
谓词
P(v,w)
定义了弧
的意义或信息
}
基本操作
P
：
CreatGraph(&G,V,VR)
初始条件：
V
是图的顶点集，
VR
是图中弧的集合
操作结果：按
V<
/p>
和
VR
的定义构造图
G
DestroyGraph(&G)
初始条件：图<
/p>
G
存在
操作结果：销毁图
G
InsertVex(&G,v)
初始条件：图
G
存在，
v
和图中顶点有相
同特征
操作结果：在图
G
中增添新顶点
v
……
InsertArc(&G,v,w)
初始条件：图
G
存在，
v
和
w
是
G
中两个顶点
操作结果：在
G
中增添弧
，若
G
是无向的则还增添对称弧
……
DFSTraverse(G,Visit())
初始条件：
图
G
存在，
Visit
是顶点的应用函数
操作结果：
对图进行
深度优先遍历
，
在遍历过程
中对每个顶点调用函数
Visit
一次且仅一次。
一旦
Visit()
失败，则操作失败
BFSTraverse(G,Visit())
初始条件：图
G
存在，
Visit<
/p>
是顶点的应用函数
操作结果：
对图进行
广度优先遍历
，
在遍历过程中对每个顶点调用函数
Visit
一次且仅一次。
一旦
Visit()
失败，则操作失败
}
ADT
Graph
栈的抽象数据类型定义：
ADT
Stack
{
数据对象
：
D={ai|ai
∈
ElemSet,i=1,2
,
…
,n,n
≥
0}
数据关系
：
R1={
∈
D,i=2,
< br>…
,n}
约定
an
端为栈顶，
ai
端为栈底
基本操作
：
InitStack(&S)
操作结果：构造一个空栈
S
DestroyStack(&S)
初始条件：栈
S
已存在
操作结果：将
S
清为空栈
StackEmpty(S)
初始条件：栈
< br>S
已存在
操作结果：若栈
S
为空栈，则返回
TRUE
，否则
FALSE
……
Push(&S,e)
初始条件：栈
S
已存在
操作结果：插入元素
e
为新的栈顶元素
Pop(&S,&e)
初始条件：栈
S
已存在且非空
操作结果：删除
S
的栈顶元素，并用
e
返回其值
StackTraverse(S,visit())
初始条
件：栈
S
已存在且非空
操作结果：从栈底到栈顶依次对
S
的每个数据元素调
用函数
visit()
，一旦
visi
t()
失败，
则操作失效
}
ADT
Stack
队列的抽象数据类型定义：
ADT Queue
{
数据对象
：
D={a
i
|a
i
∈
ElemSet,i=1,2,<
/p>
…
,n,n
≥
0
}
数据关系
：
Rl={
i-1
,a
i
>|a<
/p>
i-1
,a
i
∈
D,i=2,
…
,n}
约定其中
a
i
端为队列头，
a
n
端为队列尾。
基本操作
：
InitQueue(&Q)
操作结果：构造一个空队列
Q
DestroyQueue(&Q)
初始条件：队列
Q
已存在
操作结果：
队列
Q
被销毁，不再存在
QueueEmpty(Q)
初始条件：队列
Q
已存在
操作结果：若
Q
为空队列，则返回
TRUE
，否则
FALSE
……
EnQueue(&Q,e)
初始条件：队列
Q
已存在
操作结果：插入元
素
e
为
Q
的新
的队尾元素
DeQueue(&Q,&e)
初始条件：
Q
为非空队列
<
/p>
操作结果：删除
Q
的队头元素，并用
e
返回其值
}
ADT
Queue
2
．主程序的流程：
调用
CreateDN
函数创建图的邻接表
G
；
调用
PrintDN
函数输出邻接表
G
< br>；
调用
DFSTravers
e
函数深度优先遍历图；
调用
BFSTraverse
函数广度优先遍历图
3
．函数关系调用图：
LocateVex
main
Visit
FirstAdjVex
CreateDN
NextAdjVex
InitStack
PrintDN
InitQueue
StackEmpty
DFSTraverse
EnQueue
GetTop
QueueEmpty
Push
BFSTraverse
DeQueue
Pop
主程序
3
．调试分析
（
1
）书上给出了图的广度优先非递归遍历算法，主要是要实
现里面的
FirstAdjVex(G,u)
和
NextAdjVex(G,u,w)
函数。我刚开始编写的这两个函数分别为
：
int FirstAdjVex(ALGraph
G
,int u){
return LocateVex(G
,G
.vertices[u].firstarc->adj
vex);
}
int
NextAdjVex(ALGraph G
,int u,int w){
ArcNode *p=es[u].firstarc;
w
hile(LocateVex(G
,p->adjvex)!=w)p=p->nex
tarc;
p=p->nextarc;
if(!p)return -1;
return
LocateVex(G
,p->adjvex);
}
对于书上给出的
BFSTraverse
函
数这样没有问题。但当我仿照
BFSTraverse
函数编出
了
DFSTraverse
函数后就有问题了。经过分析我把以
上两个函数稍作了改动：
int
FirstAdjVex(ALGraph G
,int u){
if(!G
.vertices[u].firstarc)return -1;
return LocateVex(G
,G
< br>.vertices[u].firstarc->adjvex);
}
int NextAdjVex(ALGraph
G
,int u,int w){
ArcNode
*p=es[u].firstarc;
while(p&&LocateVex(G
,p->adjvex)!=w)p=p->nextarc;
if(!p)return FirstAdjVex(G,u);
p=p->nextarc;
if(!p)return
-1;
return
LocateVex(G
,p->adjvex);
}
（
2
）算法
的时间复杂度分析：
遍历图的过程实质上是对每个顶点查找其
邻接点的过程，
其耗费的时间取决于所采用的存储
结构。
当以邻接表作图的存储结构时，
找邻接点所需时间为
< br>O(e)
，
其中
e
为无向图的边数或
有向图的弧数。
由此，
当以邻接表作存储结构时，
深度优先搜索遍历图的时间复杂度为
O(n+e)
广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，
两者不同之处仅仅在于对顶点
访问的顺序不同。
4
．测试结果
用需求分析中的测试数据
输入：
输出：
5
、用户手册
（
1
）输入顶点数和弧数；
（
2
）输入顶点内容；
-
-
-
-
-
-
-
-
-
上一篇：图的遍历与最小生成树的实现
下一篇：图的基本操作与实现的课程设计报告