【文件属性】：
文件名称：实现图的遍历算法 深度优先遍历
文件大小：124KB
文件格式：DOC
更新时间：2013-12-19 05:08:42
实现图的遍历算法
2． 系统设计
1．用到的抽象数据类型的定义
图的抽象数据类型定义：
ADT Graph{
数据对象V：V是具有相同特性的数据元素的集合，称为顶点集
数据关系R：
R={VR}
VR={|v,w∈V且P(v,w),表示从v到w的弧，
谓词P(v,w)定义了弧的意义或信息}
基本操作P：
CreatGraph(&G,V,VR)
初始条件：V是图的顶点集，VR是图中弧的集合
操作结果：按V和VR的定义构造图G
DestroyGraph(&G)
初始条件：图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是顶点的应用函数
操作结果：对图进行广度优先遍历，在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦Visit()失败，则操作失败
}ADT Graph
栈的抽象数据类型定义：
ADT Stack{
数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}
数据关系：R1={|ai-1,ai∈D,i=2,…,n}
约定an端为栈顶，ai端为栈底
基本操作：
InitStack(&S)
操作结果：构造一个空栈S
DestroyStack(&S)
初始条件：栈S已存在
操作结果：将S清为空栈
StackEmpty(S)
初始条件：栈S已存在
操作结果：若栈S为空栈，则返回TRUE，否则FALSE
……
Push(&S,e)
初始条件：栈S已存在
操作结果：插入元素e为新的栈顶元素
Pop(&S,&e)
初始条件：栈S已存在且非空
操作结果：删除S的栈顶元素，并用e返回其值
StackTraverse(S,visit())
初始条件：栈S已存在且非空
操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()，一旦visit()失败，则操作失效
}ADT Stack
队列的抽象数据类型定义：
ADT Queue{
数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}
数据关系：Rl={|ai-1,ai∈D,i=2,…,n}
约定其中ai端为队列头，an端为队列尾。
基本操作：
InitQueue(&Q)
操作结果：构造一个空队列Q
DestroyQueue(&Q)
初始条件：队列Q已存在
操作结果：队列Q被销毁，不再存在
QueueEmpty(Q)
初始条件：队列Q已存在
操作结果：若Q为空队列，则返回TRUE，否则FALSE
……
EnQueue(&Q,e)
初始条件：队列Q已存在
操作结果：插入元素e为Q的新的队尾元素
DeQueue(&Q,&e)
初始条件：Q为非空队列
操作结果：删除Q的队头元素，并用e返回其值
}ADT Queue
2．主程序的流程：
调用CreateDN函数创建图的邻接表G；
调用PrintDN函数输出邻接表G；
调用DFSTraverse函数深度优先遍历图；
调用BFSTraverse函数广度优先遍历图
