文件名称：图的深度广度优先算法
文件大小：4KB
文件格式：CPP
更新时间：2011-05-28 15:21:00
C语言 图 广度优先 数据结构 深度优先
本演示程序中，要求以邻接表作为图的存储结构。图中顶点数据类型为字符型，在提示信息下由用户输入。边的信息由用户输入弧头和弧尾元素。
为实现上述程序功能，以线性链表表示集合。为此，需要两个抽象数据类型：线性表和集合。
１． 线性表的抽象数据类型定义为：
ADT ALGraph{
数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。
数据关系R1：R={VR}
VR={
基本操作P：
void CreateAdjList(ALGraph& G)
操作结果：根据相应的提示信息构造一个图。
int LocateVex(&G,char u)
初始条件：图G存在，u和G中顶点有相同特征。
操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1。
int FirstAdjVex(ALGraph G,int v)
初始条件：图G存在，v是G中某个顶点。
操作结果：返回v第一个邻接顶点。若v在G中没有邻接顶点，返回-1。
int NextAdjVex(ALGraph G,int v,int w)
初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。
操作结果：返回v的（相对于w的）第一个邻接顶点。若不存在，返回-1。
void DFS(ALGraph &G,int v)
初始条件：图G存在。
操作结果：从顶点v出发，对图进行深度优先遍历。
void DFSTraverse(ALGraph *G)
初始条件：图G存在。
操作结果：对图进行深度优先遍历。
void BFSTraverse(ALGraph *G)
初始条件：图G存在。
操作结果：对图进行广度优先遍历。
}ADT ALGraph
２． 队列的抽象数据类型定义为：
ADT Queue{
数据对象D：D={ | QNodeSet,i=1,2,…,n,n 0 }
数据关系R2：R2={< , >| , D1, i=2,…,n}
约定其中 端为队列头， 为队列尾
基本操作P：
InitQueue (*Q)
操作结果：构造一个空队列Q
EnQueue (*Q,e)
初始条件：队列Q已存在
操作结果：插入元素e为Q的新的队尾元素
DeQueue (*Q)
初始条件：Q为非空队列
操作结果：删除Q的队头元素，并返回其值
QueueEmpty (*Q)
操作结果：队为空，则返回0；否则，返回1
}ADT Queue
图的基本操作设置如下：
void CreateAdjList(ALGraph& G) //构建图
int LocateVex(ALGraph &G,char u) //返回u在G中的位置
int FirstAdjVex(ALGraph G,int v) //返回v的第一个邻接节点
int NextAdjVex(ALGraph G,int v,int w) //返回v的相对w的下一个邻接节点
void DFS(ALGraph &G,int v) //从顶点v开始深度优先遍历图
void DFSTraverse(ALGraph *G) //深度优先遍历图
void BFSTraverse(ALGraph *G) //广度优先遍历图
队列的基本操作设置如下：(具体操作上一次上机题中已经涉及，故此处不再详述)
void InitQueue(LinkQueue &Q)
void EnQueue(LinkQueue& Q,int e)
int DeQueue( LinkQueue& Q)
int QueueEmpty(Queue *Q)