2012级计算机科学与技术专业
《数据结构》
课程设计文档
设计题目 图的遍历
班 级 12网路工程
组长学号 ********** 姓名 庄俊坤
心的组词学 号 ********** 姓名如何受精 林捷
学 号 ********** 姓名 周柏煌
学 号 ********** 姓名 赵云鹏
学 号 ********** 姓名 谢国印
完成日期 2014.1
前言
图遍历又称图的遍历，属于数据结构中的内容。指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。
一、设计题目
图遍历的演示
二、实验目的：
本课程设计是《数据结构》课程的组成之一，也是它的继续和延伸。采用集中学习方法，分组完成一个小型应用系统。开设本课程的目的是使学生通过参加小型软件的开发过程，进一步了解并掌握数据结构与算法的设计方法，具备初步的分析和设计能力；同时培养学生的创新能力和创新意识，锻炼他们的团队协作精神。
三、问题描述：
由于图结构本身的复杂性，所以图的遍历操作也较复杂，主要表现在以下四个方面：
① 在图结构中，没有一个“自然”的首结点，图中任意一个顶点都可作为第一个被访问的结点。
② 在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。
代理成本理论③ 在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。
④ 在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。
四、功能要求
（1）以邻接表作为存储结构；
（2）由用户指定遍历的起点；
（3）实现深度优先和广度优先遍历；
（4）输出深度优先遍历和广度优先遍历的结点访问序列；
（5）并给出相应生成树的边集。
（6）给出至少3组测试数据，其中图顶点的个数大于10小于30。
较高要求：建立深度和广度生成树，按凹入表或树形打印生成树。
五、相关原理
(1如何月入过万)深度优先搜索法﹕
深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。其递归算法如下：
Boolean visited[MAX_VERTEX_NUM]; //访问标志数组
Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数
void DFSTraver (Graph G, Status(*Visit)(int v)){
VisitFunc = Visit;人生目标作文
for(v=0; v<G.vexnum; ++v)
visited[v] = FALSE; //访问标志数组初始化
for(v=0; v<G.vexnum; ++v)
if(!visited[v])
DFS(G, v); //对尚未访问的顶点调用DFS
}
void DFS(Graph G, int v){ //从第v个顶点出发递归地深度优先遍历图G
visited[v]=TRUE; VisitFunc(v); //访问第v个顶点
for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))
//FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空（0）。
//若w是v的邻接顶点，NextAdjVex返回v的（相对于w的）下一个邻接顶点。
说梦话的原因 //若w是v的最后一个邻接点，则返回空（0）。
if(!visited[w])
DFS(G, w); //对v的尚未访问的邻接顶点w调用DFS
}
(2)广度优先搜索法﹕
图的广度优先搜索是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2,…, vi t，并均标记已访
问过，然后再按照vi1,vi2,…, vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。其非递归算法如下：
Boolean visited[MAX_VERTEX_NUM]; //访问标志数组电气及其自动化
Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数
void BFSTraver (Graph G, Status(*Visit)(int v)){
VisitFunc = Visit;
for(v=0; v<G.vexnum, ++v)
visited[v] = FALSE;
initQueue(Q); //置空辅助队列Q
for(v=0; v<G.vexnum; ++v)
if(!visited[v]){
visited[v]=TRUE; VisitFunc(v);
EnQueue(Q, v); //v入队列
while(!QueueEmpty(Q)){
生活中的痛点 DeQueue(Q, u); //队头元素出队并置为u
for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w))
