图的深度优先遍历C

1/21西北师范大学地环学院地理信息系数据结构实验讲义十图的存储与深度优先遍历张长城2011-2-8[图存储以及深度优先遍历算法分析，C语言实现]2/21实验任务描述1用C语言邻接矩阵完成图的存储；2分析深度优先遍历算法；3用C语言实现图的深度优先遍历；4深度优先遍历应用：图的关节点计算。3/21一、邻接矩阵存储图的深度优先遍历过程分析对图1这样的无向图，要写成邻接矩阵，则就是下面的式子图1顶点矩阵：V=87654321VVVVVVVV弧长矩阵：A=0000011000110001001010001000000100000111000000110000001100011000一般要计算这样的问题，画成表格来处理是相当方便的事情，实际中计算机处理问题，也根本不知道所谓矩阵是什么，所以画成表格很容易帮助我们完成后面的编程任务。在我们前面介绍的内容中，有不少是借助着表格完成计算任务的，如Huffman树。V1（1）V2（2）V3（3）V4（4）V5（5）V6（6）V7（7）V8（8）V1（1）01100000V2（2）10011000V3（3）10000110V4（4）01000001V5（5）01000001V6（6）00100010V7（7）00100100V8（8）00011000表1图1的邻接矩阵表为了记录那些顶点是已经走过的，还要设计一个表来标记已经走过的顶点，在开始，我们假设未走过的是0，走过的是1，于是有：V1V2V3V4V5V6V7V800000000表2图1的顶点访问表Visited4/21深度优先遍历过程如下：（1）从第1行开始，寻找和V1相连的第1个顶点，首先在Visited表中标记V1被访问到，就是：V1V2V3V4V5V6V7V810000000表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）01100000V2（2）10011000表4图1的邻接矩阵表深度优先遍历步骤(1)（2）然后则转向V2顶点所在的行，意味着我们已经抵达V2，再次在Visited表中标记V2顶点已经被访问，就是：V1V2V3V4V5V6V7V811000000表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）01100000V2（2）10011000V4（4）01000001表6图1的邻接矩阵表深度优先遍历步骤(2)（3）然后则转向V4顶点所在的行，意味着我们已经抵达V4，再次在Visited表中标记V4顶点已经被访问，就是：V1V2V3V4V5V6V7V811010000表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）01100000V2（2）10011000V4（4）01000001V8（8）00011000表8图1的邻接矩阵表深度优先遍历步骤(3)5/21（4）然后则转向V8顶点所在的行，意味着我们已经抵达V8，再次在Visited表中标记V8顶点已经被访问，就是：V1V2V3V4V5V6V7V811010001表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）01100000V2（2）10011000V4（4）01000001V8（8）00011000V5（5）01000001表10图1的邻接矩阵表深度优先遍历步骤(4)（5）然后则转向V5顶点所在的行，意味着我们已经抵达V5，再次在Visited表中标记V5顶点已经被访问，就是：V1V2V3V4V5V6V7V811011001表11图1的顶点访问表Visited深度优先遍历步骤(5)寻找连接V5的、并且是未被访问过的第一个顶点，此处未找到，注意V2、V8顶点已经在Visited表中标记已访问过。V1（1）V2（2）V3（3）V4（4）V5（5）V6（6）V7（7）V8（8）V1（1）01100000V2（2）10011000V4（4）01000001V8（8）00011000V5（5）01000001表12图1的邻接矩阵表深度优先遍历步骤(4)（5）这个地方一定注意：V5上找不到未访问过的顶点，说明此路到此就算走死了。此时看Visited表：其中还有顶点没有抵达过，于是要按原路返回，所谓原路就是从表12、表10、表9走过的路线返回、然后逐个查找这些顶点上有无未抵达过的顶点。过程如下：再次从V5返回到V8，查找V8上有无未抵达过的顶点，结果是无；再次从V8返回到V4，查找V4上有无未抵达过的顶点，结果是无；再次从V4返回到V2，查找V2上有无未抵达过的顶点，结果是无；再次从V2返回到V1，查找V1上有无未抵达的顶点，结果是V3，于是重复第(1)步，首先标记V3访问到：标记V1-V3，标记Visited表V3被访问：V1V2V3V4V5V6V7V811111001表13图1的顶点访问表Visited深度优先遍历步骤(4)6/21到V3，就是这样的情况：V1（1）V2（2）V3（3）V4（4）V5（5）V6（6）V7（7）V8（8）V1（1）01100000V2（2）10011000V4（4）01000001V8（8）00011000V5（5）01000001V3（3）10000110表14图1的邻接矩阵表深度优先遍历步骤(5)（6）到达V3后，寻找第一个未被访问过的顶点：V6，首先标记Visited表，说明已经抵达V6，就是：V1V2V3V4V5V6V7V811111101表15图1的顶点访问表Visited深度优先遍历步骤(6)再从V6开始找下一个顶点就是V7：V1（1）V2（2）V3（3）V4（4）V5（5）V6（6）V7（7）V8（8）V1（1）01100000V2（2）10011000V4（4）01000001V8（8）00011000V5（5）01000001V3（3）10000110V7（7）00100100表16图1的邻接矩阵表深度优先遍历步骤(6)（7）在Visited表中标注V7已经访问到，就是：V1V2V3V4V5V6V7V811111111表17图1的顶点访问表Visited深度优先遍历步骤(7)至此，图1的深度优先遍历完成。7/21二、结果分析从上面的过程可以看出：仅仅就顶点访问到的次序而言，图1的深度优先遍历结果是：V1-V2-V4-V8-V5-V3-6-V7但实际执行过程中我们可以发现：所谓图的遍历、其结果应该是一个树：图2深度优先遍历生成树在C语言中，显示这个结果并不容易，所以大多教材中并不会给出这样的结果。三、C语言编程实现图的深度优先遍历图1只有8个顶点，可在实际中，一个图的顶点个数是不确定的，在编程中要保存顶点数据、邻接矩阵，首先就要考虑动态数组；其次，为了方便邻接矩阵的输入和修改，最好是把数据保存在文本文件中。在我们的教材中、程序使用了键盘输入的方式，而在实际操作中、在图的顶点个数比较多的情况下，手工无差错输入很多数据、几乎是无法办到的事情，为此，我们在文件p176G719.txt中保存了图1的邻接矩阵数据。这个文件的名称含义是：教材176页图7.19的顶点名称和邻接矩阵数据。有了这样的数据文件，在记事本程序中可以很方便的修改和补充数据。这个文件的内容如下：12345678910111213141516178V1V2V3V4V5V6V7V80110000010011000100001100100000101000001001000100010010000011000表18p176G719.txt文件内容这个文件第一行是8，说明这个图有8个顶点，随后在第2行到第9行，则是图的顶点8/21名称，第10行到末尾，则是该图的邻接矩阵。根据不同的图，在记事本程序中完成这样的数据是非常简单的事情，哪怕错了再修改也是很容易做到。1设计图的存储结构以及数据文件读取图的存储、无论哪种方法，都是由两部分组成的，一个是顶点名称集合，一个是顶点关系集合，在邻接矩阵方式中，顶点名称是一个字符串数组，而顶点关系则是一个矩阵、这个矩阵在C语言中是一个二维数组。于是图的结构可以是：structGraph{intA[100][100];//邻接矩阵charV[100][20];//顶点名称矩阵，100行，每个名称字符串不超过20字节intnum;//顶点个数intVisited[100];//访问记录表};但这样的定义很死板，它假设程序最大是100个顶点，实际我们的教材中就是这么定义的。但幸好我们前面已经知道该怎么处理二维数组，于是这里我们可以动态申请内存，以保证在很多顶点的情况也能使用，对二维数组，则上述定义变为：structGraph{int**pA;//邻接矩阵指针char**pV;//顶点名称指针intnum;//顶点个数int*Visited;//访问记录表指针};对这样数组的构造，参见第5部分：数组，好在我们前面有过介绍。回忆一下，如有数组：intA[3][3]={{1,2,3},{4,5,6},{7,8,9}};则A[0]、A[1]、A[2]则代表每一行的地址，一般称为行首地址，比如这三行行首地址分别是[100]、[200]、[300]，这三个地址数据分别存储在地址[2000]、[2001]、[2002]的存储空间里，则地址[2000]就是这个数组A的含义，就是所谓行首地址数组的首地址。反过来，如:int*p[3];p[0]=A[0];p[1]=A[1];p[2]=A[2];上面的式子里，如p[0]地址为[3000]、[3001]、[3002]，其中的内容保存的是100、200、300，这样就相当于保存了A数组的行首地址，所以p就是个二维数组行首指针数组，只不过它仅仅是三行的二维数组。如把p[0]的地址给另外一个指针变量pA，则pA就是：int**pA;假如这个变量的地址在[5000]，给这个变量赋值：pA=&p[0];于是地址[5000]中将存储3000，这里pA和A的含义是一致的。实际数组A本身就是地址[5000]，如有以下语句：X=A[1][2];就是从A的地址[5000]、读到内容3000、再从3001读到200、再从200后取第1个数，过程如下图3所示：9/21图3二维数组的数据读取过程针对n个顶点，则初始化一个图的函数就是：1234567891011121314151617181920#defineVLENGTH20//定义每个顶点名称不超过20字节structGraph*GraphInit(intn){inti;structGraph*g;if(n=0)returnNULL;g=(structGraph*)malloc(sizeof(structGraph));g-num=n;g-pA=(int**)malloc(sizeof(int)*n);g-pV=(char**)malloc(sizeof(char)*n);for(i=0;in;i++){g-pA[i]=(int*)malloc(sizeof(int)*n);g-pV[i]=(char*)malloc(sizeof(char)*VLENGTH);}g-Visite