图的深度优先遍历C剖析.doc

西北师范大学地环学院地理信息系 数据结构实验讲义 十 图的存储与深度优先遍历 张长城 2011-2-8 [图存储以及深度优先遍历算法分析，C语言实现] 实验任务描述 1 用C语言邻接矩阵完成图的存储； 2 分析深度优先遍历算法； 3 用C语言实现图的深度优先遍历； 4 深度优先遍历应用：图的关节点计算。 邻接矩阵存储图的深度优先遍历过程分析 对图1这样的无向图，要写成邻接矩阵，则就是下面的式子 图 1 顶点矩阵：V= 弧长矩阵： A= 一般要计算这样的问题，画成表格来处理是相当方便的事情，实际中计算机处理问题，也根本不知道所谓矩阵是什么，所以画成表格很容易帮助我们完成后面的编程任务。在我们前面介绍的内容中，有不少是借助着表格完成计算任务的，如Huffman树。 V1（1） V2（2） V3（3） V4（4） V5（5） V6（6） V7（7） V8（8） V1 （1） 0 1 1 0 0 0 0 0 V2 （2） 1 0 0 1 1 0 0 0 V3 （3） 1 0 0 0 0 1 1 0 V4 （4） 0 1 0 0 0 0 0 1 V5 （5） 0 1 0 0 0 0 0 1 V6 （6） 0 0 1 0 0 0 1 0 V7 （7） 0 0 1 0 0 1 0 0 V8 （8） 0 0 0 1 1 0 0 0 表1 图1的邻接矩阵表 为了记录那些顶点是已经走过的，还要设计一个表来标记已经走过的顶点，在开始，我们假设未走过的是0，走过的是1，于是有： V1 V2 V3 V4 V5 V6 V7 V8 0 0 0 0 0 0 0 0 表2 图1的顶点访问表Visited 深度优先遍历过程如下： （1）从第1行开始，寻找和V1相连的第1个顶点，首先在Visited表中标记V1被访问到，就是： V1 V2 V3 V4 V5 V6 V7 V8 1 0 0 0 0 0 0 0 表3 图1的顶点访问表Visited 深度优先遍历步骤(1) 在该行，我们找到的第一个连接顶点是V2，找到V2顶点后，记录：V1-V2，意味着我们已经抵达V2，注意修改邻接矩阵表； V1（1） V2（2） V3（3） V4（4） V5（5） V6（6） V7（7） V8（8） V1 （1） 0 1 1 0 0 0 0 0 V2 （2） 1 0 0 1 1 0 0 0 表4 图1的邻接矩阵表 深度优先遍历步骤(1) （2）然后则转向V2顶点所在的行，意味着我们已经抵达V2，再次在Visited表中标记V2顶点已经被访问，就是： V1 V2 V3 V4 V5 V6 V7 V8 1 1 0 0 0 0 0 0 表5 图1的顶点访问表Visited 深度优先遍历步骤(2) 然后，寻找连接V2的、并且是未被访问过的第一个顶点，就是V4：记录V2-V4； V1（1） V2（2） V3（3） V4（4） V5（5） V6（6） V7（7） V8（8） V1 （1） 0 1 1 0 0 0 0 0 V2 （2） 1 0 0 1 1 0 0 0 V4 （4） 0 1 0 0 0 0 0 1 表6 图1的邻接矩阵表 深度优先遍历步骤(2) （3）然后则转向V4顶点所在的行，意味着我们已经抵达V4，再次在Visited表中标记V4顶点已经被访问，就是： V1 V2 V3 V4 V5 V6 V7 V8 1 1 0 1 0 0 0 0 表7 图1的顶点访问表Visited 深度优先遍历步骤(3) 然后则转向V4顶点所在的行，寻找连接V4的、并且是未被访问过的第一个顶点，就是V8：记录V4-V8； V1（1） V2（2） V3（3） V4（4） V5（5） V6（6） V7（7） V8（8） V1 （1） 0 1 1 0 0 0 0 0 V2 （2） 1 0 0 1 1 0 0 0 V4 （4） 0 1 0 0 0 0 0 1 V8 （8） 0 0 0 1 1 0 0 0 表8 图1的邻接矩阵表 深度优先遍历步骤(3)  （4）然后则转向V8顶点所在的行，意味着我们已经抵达V8，再次在Visited表中标记V8顶点已经被访问，就是： V1 V2 V3 V4 V5 V6 V7 V8 1 1 0 1 0 0 0 1 表9 图1的顶点访问表Visited 深度优先遍历步骤(4) 然后则转向V8顶点所在的行，寻找连接V8的、并且是未被访问过的第一个顶点，就是V5：记录V8-V5； V1（1） V2（2） V3（3） V4（4） V5（5） V6（6） V7（7） V8（8） V1 （1） 0 1 1 0 0 0 0 0 V2 （2） 1 0 0 1 1 0 0