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