课程设计说明书 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。然后读入顶点对
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
沈 阳 大 学