图的深度周游 下载本文

内容发布更新时间 : 2024/12/25 11:12:42星期一 下面是文章的全部内容请认真阅读。

课程设计说明书 No.1

一、 课程设计的目的与意义 本课程设计是为了配合《数据结构》课程的开设,通过设计一完整的程序,使学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并用TC上机调试的基本方法。 从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次。这个过程就叫图的遍历。图的遍历算法是图的连通性问题、拓扑排序和求关键路径等算法的基础。通常有两条遍历途径:深度优先遍历和广度优先遍历。此课设就主要探讨深度优先遍历。深度优先遍历类似于树的先根遍历,是树的先跟遍历的推广。 二、设计方案论证 2.1设计思路 假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶点均已被访问为止。 图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地,用此方法遍历图就很自然地称之为图的深度优先遍历。 邻接表(Adjdcency List):是图的一种顺序存储结构和链式存储结构相结合的存储方法。我们可以根据邻接表来查找图的深度遍历,可以更容易的让人们知道深度优先遍历,更加清晰地知道图的深度遍历的来源。 2.1.1邻接表的结构 就是对于图G中的每个顶点Vi,将邻接于Vi的所有顶点Vj链成一个单链表,单链表中的节点称为表节点,这个单链表就称为顶点Vi的邻接表。对应于每个 1

沈 阳 大 学

课程设计说明书 No.2

顶点的邻接表建立一个头节点,这些头节点通常以顺序结构的形式存储(也可以链式)。为便于访问,可以将所有点的邻接表的头节点放到一个数组中,于是图就可以由这个头节点数组表示,这个头节点数组称为顶点表。因此,在图的邻接表表示中有两种节点结构:一种是顶点表的节点结构(头节点结构),其结构为其中vertex域存放与顶点Vi有关的信息,firstedge为指针域,存放与该结点相邻接的所有顶点组成的单链表的头指针;另一种是单链表的表节点结构,由存放与顶点Vi相邻接的顶点在二维数组中的序号的邻接顶点域(adjvex)和指向与顶点Vi相邻接的下一个顶点的表节点的指针域(next)所组成。对于带权图,表节点还增设一个权值域info。 邻接表是图的一种链式存储结构为,类似于树的孩子链表表法。在邻接表中,对图中每个顶点建立一个单链表,n个顶点,就要建n个链表。对于无向图,第i个单链表中的结点表示依赖于顶点vi的边。对于有向图是以顶点vi为尾的弧,这个单链表称为顶点vi的单链表(即Vi的邻接表)。单链表中每一个结点称为表结点,应包括两个域:邻接点域,用以存放与vi相邻接的顶点序号;链域用以指向民vi邻接的下一个结点。另外,每一个单链表设一个表头结点。每一个表头结点有两个域,一个用来存放顶点vi的信息;另一个域用来指向vi的邻接表中的第一个结点。为了便于管理和随机访问任一顶点的单链表,将所有单链表的头结点组织成一个一维数组。 表结点 头结点 建立邻接表的方法是:首先将邻接表表头数组初始化,第i个表头的vertex初始化为i,;link初始化为NULL。然后读入顶点对,产生一个表结点,将j放入到该结点的adjvex域,将该结点链到邻接表的表头的T第i个表头的link域上。 2.1.2深度优先遍历的递归定义 假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,并将其标记 2

adjvex nextarc info data firstarc 沈 阳 大 学

课程设计说明书 No.3

为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶点均已被访问为止。 图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地,用此方法遍历图就很自然地称之为图的深度优先遍历。 2.1.3 深度优先搜索的过程 (1)基本思想: 首先访问图中某一个指定的出发点Vi; 然后任选一个与顶点Vi相邻的未被访问过的顶点Vj; 以Vj为新的出发点继续进行深度优先搜索,直至图中所有顶点均被访问过。 (2)具体过程: 设x是当前被访问顶点,在对x做过访问标记后,选择一条从x出发的未检测过的边(x,y)。若发现顶点y已访问过,则重新选择另一条从x出发的未检测过的边,否则沿边(x,y)到达未曾访问过的y,对y访问并将其标记为已访问过;然后从y开始搜索,直到搜索完从y出发的所有路径,即访问完所有从y出发可达的顶点之后,才回溯到顶点x,并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时,若x不是源点,则回溯到在x之前被访问过的顶点;否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过,若图G是连通图,则遍历过程结束,否则继续选择一个尚未被访问的顶点作为新源点,进行新的搜索过程。 2.1.4 深度优先遍历图的邻接表 假设初始状态是图中所有顶点未曾被访问,深度优先遍历可以从图的初始点出发,访问初始点,然后依次从v未被访问的邻接点出发深度优先遍历图,直至图中所有和v有路径相通的顶点都被访问到;若此时仍有顶点未被访问到,则从 另一个未被访问的顶点出发,重复上述过程,直至所有点都被访问到为止。这是 3

沈 阳 大 学