图的深度遍历和广度遍历图的深度遍历和广度遍历学生姓名：学生姓名： 指导老师：肖增良指导老师：肖增良摘 要：数据结构是一门专业基础课，学习数据结构要求我们学会研究计算机加工的数据结构特性，以便为应用涉及的数据结构选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的的技术,图是应用最广泛的数学结构。图的遍历和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。对于广度优先遍历应利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）来实现。首先建立一空队列，从初始点出发进行访问，当被访问时入队，访问完出队。并以队列是否为空作为循环控制条件。对于深度优先遍历则采用递归或非递归算法来实现。关键词 图 遍历 深度 广度 队列 算法目目 录录1.课程设计的要求 32.设计方案 4 2.1 图的初始化 42.2 深度优先搜索的基本思想4 2.3 广度优先搜索的基本思想 62.4 图的深度优先搜索和广度优先搜索的定义 73.图的遍历模块化 83.1 图的存储结构 83.2 邻接表的定义和初始化 93.3BDF 和 DBF 编码 10 4图的遍历流程图 13 4.2 图的深度优先遍历流程134.2 图的广度优先遍历流程图145系统运行运行环境与结果155.1 运行环境155.2 结构图图及运行结果166课程设计总结17参考文献18附录：源程序代码191 1 课程设计的要求课程设计的要求该课题要求我们熟悉图，图是一种较为线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每一个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（即其孩子结点）有关，但只能和上一层中一个元素（即双亲结点）有关；而在图形结构中，节点之间的的关系是任意的，图中任意两个数据元素之间都可能相关。图的应用极为广泛，特别是近年来的迅速发展，已经渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及其他的分支中。图的遍历算法是求解图的连通性问题、拓扑排序和求解关键路径等算法的基础。而深度遍历优先搜索和广度遍历优先搜索是遍历图的最基本的两条途径。因此，本课程要求我们能熟练地掌握深度优先搜索遍历和广度优先搜索遍历的方法对图进行搜索。2 2 设计方案设计方案2.12.1图的初始化图的初始化typedef VertexNode AdjListMaxVertexNum; /*AdjList 是邻接表类 typedef struct node /*边表结点*/int adjvex; /*邻接点域*/struct node *next; /*链域*/EdgeNode;typedef struct vnode /*顶点表结点*/char vertex; /*顶点域*/EdgeNode *firstedge; /*边表头指针*/VertexNode;型*/typedef struct AdjList adjlist; /*邻接表*/int n,e; /*图中当前顶点数和边数*/ ALGraph; /*图类型*/2.22.2 深度优先搜索的基本思想深度优先搜索的基本思想深度优先搜索是一种递归的过程，正如算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。假设给定图 G 的初态是所有顶点均未曾访问过。在 G 中任选一顶点 v 为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点 v，并将其标记为已访问过；然后依次从 v 出发搜索 v 的每个邻接点 w。若 w 未曾访问过，则以 w为新的出发点继续进行深度优先遍历，直至图中所有和源点 v 有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。比如设 x 是当前被访问顶点，在对 x 做过访问标记后，选择一条从 x出发的未检测过的边(x，y)。若发现顶点 y 已访问过，则重新选择另一条从 x 出发的未检测过的边，否则沿边(x，y)到达未曾访问过的 y，对 y 访问并将其标记为已访问过；然后从 y 开始搜索，直到搜索完从 y 出发的所有路径，即访问完所有从 y 出发可达的顶点之后，才回溯到顶点 x，并且再选择一条从 x 出发的未检测过的边。上述过程直至从 x 出发的所有边都已检测过为止。此时，若 x 不是源点，则回溯到在 x 之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图 G 是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。其具体过程如下图所示图 2.1 图的深度优先遍历(1)访问 vo, 记录 visited0=True, 从 v0 的一个未被访问过的邻接点 v1 出发进行遍历(2)访问 v1, visited1=True,从 v1 的一个未被访问过的邻接点 v4 出发遍历(3)访问 v4, visited4=True,从 v4 的一个未被访问过的邻接点 v5 出发遍历(4)访问 v5, visited5=True,由于 v5 的两个邻接点 v1 和 v4 都被访问过，退回上一邻接点 v4，又 v4 的两个邻接点 v1 和 v5 都被访问过，再退回上一邻接点 v1,从未被访问过邻接点 V6 出发遍历(5)访问 v6, visited6=True,从 v6 的一个未被访问过的邻接点 v2 出发遍历(6)访问 v2, visited2=True,v2 所有邻接点都访问过，退回上一顶点 v6,同理，v6 退回 v1,v1 退回 v0,再从 v0 未被访问过邻接点 v3 出发遍历(7)访问 v3, visited3=True，退回 v0,因所有邻接点都访问过，再退回，结束图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。2.32.3 广度优先搜索的基本思想广度优先搜索的基本思想首先访问图中指定的起始点 Vi 并将其标记为已访问过，然后由 Vi 出发访问与它相邻接的所有顶点 Vj、 Vk，并均标记为已访问过，然后再按照Vj、Vk的次序，访问每一个顶点的所有未被访问过的邻接顶点，并均标记为已访问过，下一步再从这些顶点出发访问与它们相邻接的尚未被访问的顶点，如此做下去，直到所有的顶点均被访问过为止，其具体过程如下图所示图 2.2 图的广度优先遍历(1)访问 v0,visited0=True (2)访问 v0 所有未访问过邻接 v1 和 v2, visited1=True, visited2=True;(3)访问 v1 所有未被访问过的邻接点 v3 和 v4,v5,并将它们标记已访问过；(4)访问 v2 所有未被访问过的邻接点 v6, visited6=True；(5)访问 v3 所有未被访问过的邻接点 v7, visited7=True；(6)访问 v4 所有未被访问过的邻接点(无)(7)访问 v5 所有未被访问过的邻接点 v8, visited8=True；(8)访问 v6 所有未被访问过的邻接点(无)；(9)依次访问 v7，v8 所有未被访问过的邻接点(无)，结束。在广度优先搜索中，若对顶点 V1 的访问先于顶点 V2 的访问，则对 V1 邻接顶点的访问也先于 V2 邻接顶点的访问。就是说广度优先搜索中对邻接点的寻找具有“先进先出”的特性。因此，为了保证访问顶点的这种先后关系，需借助一个队列暂存那些刚访问过的顶点。设此队列由一个一维数组构成，数组名Queue，队首指针和队尾指针分别为 front 和 rear。假设数组足够大，不必考虑有溢出的可能性。广度优先搜索不是递归过程，不能用递归形式。2.42.4 图的深度优先搜索和广度优先搜索的定义图的深度优先搜索和广度优先搜索的定义深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图，在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续下去。当结点 v 的所有边都己被探寻过，搜索将回溯到发现结点 v 有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止。图的广度优先搜索是首先访问图中指定的起始点 Vi，并将其标记为已访问过，然后由 Vi 出发访问与它相邻接的所有顶点 Vj、 Vk，并均标记为已访问过，然后再按照 Vj、Vk的次序，访问每一个顶点的所有未被访问过的邻接顶点，并均标记为已访问过，下一步再从这些顶点出发访问与它们相邻接的尚未被访问的顶点，如此做下去，直到所有的顶点均被访问过为止3 3 图的遍历模块化图的遍历模块化3.13.1 图的存储结构图的存储结构对图中每个顶点建立一个单链表;第 i 个单链表中的头结点用以存放第 i 个顶点的值 Vi,其后的结点的 adjvex 域中存放的序号 j 表示图中第 j 个顶点 Vj 是顶点Vi 的第一个邻接点(对有向图来说表示以 Vi 为弧尾以 Vj 为弧头的弧);链表中的再下一个结点中的 adjvex 中存放的序号 k 表示图中第 k 个顶点 Vk 是顶点 Vi 的再下一个邻接点，以此类推。其具体方法如下图所示ABDC0213图 3.1 图的存储结构datat aafirstarcadjvexnextarcadjvexnextarcA21B3C0D0123图 3.1 图的存储结构3.23.2 邻接表的定义和初始化邻接表的定义和初始化临接表是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第 i 个单链表中的结点表示依附于顶点 vi 的边(对有向图是以顶点 vi 为尾的弧)。每个结点由 3 个域组成，其中邻接点域（adjvex）指示与顶点 vi 邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的结点。每个链表上附设一个表的结点，在表结点中，除了设有链域（firstarc）指向链表中的结点外，还设有存储顶点 vi，的名或其他有关的信息的数据域（data） 。adjvexnextarc图 3.2