图的广度优先遍历C

1/9西北师范大学地环学院地理信息系数据结构实验讲义十一图的广度优先遍历张长城2011-2-8[图存储以及深度优先遍历算法分析，C语言实现]2/9实验任务描述1分析广度优先遍历算法；2用C语言实现图的广度优先遍历。3/9一、邻接矩阵存储图的广度优先遍历过程分析对图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/9对广度优先遍历，还需要补充一个队列、来记录一个顶点可以抵达到的其他顶点。广度优先遍历过程如下：图2图1的图广度优先遍历过程图解二、结果分析从上面的过程可以看出：仅仅就顶点访问到的次序而言，图1的广度优先遍历结果是：V1-V2-V3V4-V5-V6-7-V8但实际执行过程中我们可以发现：所谓图的广度优先遍历、其结果应该是一个树：图3广度优先遍历生成树在C语言中，显示这个结果并不容易，所以大多C语言的教材中并不会给出这样的结果。三、C语言实现队列编程根据上面的分析，我们可以知道：要广度优先遍历图，首先要一个队列系统。队列在C语言上只能自己构造，好在我们前面有链表、有顺序表，我们可以复制过来一个链表程序构造一个队列，于是从链表程序中复制过来b5.c或者b6.c即可，我们分析队列的ADT可知，最需要的队列功能需求是：QueueInit()、EnQueue、DeQueue()、QueueEmpty()这4个函数，于是有以下队列定义：5/912345structQueue{structLinkedList*LinkQueue;intCount;};表3为广度优先遍历图准备队列见B0.c由于我们已经确定使用链表做队列，所以队列实际就是链表的换名包装，所以我们可以理解为队列就是链表的另一种应用，表3的程序就是这样的做法，所以对队列的初始化，就是：12345678structQueue*QueueInit(){structQueue*q;q=(structQueue*)malloc(sizeof(structQueue));q-LinkQueue=LinkedListInit();q-Count=0;returnq;}表4队列初始化函数见B0.c有了队列的初始化，则进入队列、实际相当于给这个链表追加一条记录，就是Append()的另类包装：12345678intEnQueue(structQueue*Q,structElemType*E){if(Q==NULL)return-1;if(E==NULL)return-2;Append(Q-LinkQueue,E);Q-Count++;return0;}表5数据E进入队列，见B0.c注意数据出队列，出队列总是把链表中第一个结点的数据给出来、并删除第一个结点，所以出队列就是：1234567891011intDeQueue(structQueue*Q,structElemType*E){structElemType*pE;if(Q==NULL)return-1;if(E==NULL)return-2;pE=LinkedListGet(Q-LinkQueue,1);ElemCopy(pE,E);LinkedListDel(Q-LinkQueue,1);Q-Count--;return0;}表6数据E出队列，见B0.c6/9出队列函数总是把第一个结点删除掉，注意队列完全可能数据出完后再次有数据进入队列，则原来的结点删除函数有Bug，这在程序开发中很正常，修改后就是：12345678910111213141516intLinkedListDel(structLinkedList*L,intn){inti;structNode*p0,*p1;if(L==NULL)return-1;if(n0||nL-Count)return-2;p0=L-Head;for(i=0;in-1;i++)p0=p0-next;p1=p0-next;p0-next=p1-next;free(p1);L-Count--;if(L-Count==0)L-Tail=L-Head;return0;}表7修改后的链表结点删除函数，见B0.c修改的这个链表结点函数、仅仅加了第14行，在过去，所以结点删除后，最后的尾巴结点指针Tail所指的存储空间被释放，导致这个指针变量不可用，现在在结点个数为0的情况下，再次让尾结点指向头结点，保证下次进入链表的数据依然正确。而判断队列是否为空则相对简单的多，就是：12345intQueueEmpty(structQueue*Q){if(Q==NULL)return-1;return!(Q-Count);}表8判断队列是否为空，见B0.c补充main()函数，测试多批次进入队列、出队列，全部程序见B0.c在我们的图遍历应用中，我们对队列的数据仅仅要求一个整数即可，而这个程序进出队列的数据有三列数据，为加强该程序可靠行，修改ElemType()，就是：123456voidElemCopy(structElemType*s,structElemType*d){d-sNo=s-sNo;//strcpy(d-sName,s-sName);//d-sAge=s-sAge;}表9数据复制函数，注视掉不需要做的事情，见B0.c在一个系统中，类似这样的修改很正常，使用已有的程序完成自己的工作，会大大加快编程的进度，使得编程工作更加流畅。而这一切都需要自己有足够的积累，有这个积累后完成这样的工作才有基础，所谓技术水平，就是不断积累的过程。下面，在图的处理中会再次体现这样的过程。7/9四、程序中加入图的处理函数我们的队列系统完成后，记着再复制一个文件，加入图的邻接矩阵读数据程序，我们这里这个程序名称是b1.c。对邻接矩阵数据的读取、并构造图的过程，在深度优先遍历程序中已完成，所以直接复制过来即可，回顾广度优先遍历算法，就是把第一个顶点先无条件装进队列，所以编写遍历BFSM函数如下：123456789101112131415voidBFSM(structGraph*G){inti,n;structQueue*Q;structElemType*p,E,e;Q=QueueInit();E.sNo=0;//设置0进队列EnQueue(Q,&E);G-Visited[0]=1;//设置0号顶点已被访问p=&e;while(!QueueEmpty(Q)){//待补充}}表10广度优先遍历图之一：第0个顶点无条件进队列，见B1.c从第11行开始，则进入真正的遍历。有这么个函数后，我们可以补充main()的测试函数就是：123456main(){structGraph*G;G=GraphCreat(p176G719.txt);BFSM(G);}表11广度优先遍历图之二：从数据文件读数并构造邻接矩阵、进入遍历函数，见B1.cmain()很短，也很简单，如有不明白的回顾下深度优先遍历函数。8/9回顾一下：就是队列Q里出队列，然后找与该顶点相连的所有顶点、在进队列，就是：123456789101112131415161718192021222324voidBFSM(structGraph*G){inti,n;structQueue*Q;structElemType*p,E,e;Q=QueueInit();E.sNo=0;EnQueue(Q,&E);G-Visited[0]=1;p=&e;while(!QueueEmpty(Q)){DeQueue(Q,p);n=p-sNo;printf(%s\n,G-pV[n]);for(i=0;iG-num;i++)if(G-pA[n][i]==1&&G-Visited[i]==0){G-Visited[i]=1;E.sNo=i;EnQueue(Q,&E);}}}表12广度优先遍历图之三：出队列并找到与该顶点相连的顶点、再进队列。见B1.c运行这个程序、就会打印出这个图的广度优先遍历结果。五、结果的再次分析有了这个函数后，构造main()开始从第0个顶点遍历图1，就是：进一步测试该函数，按图1的数据仔细分析下它的执行过程，如有图的连接分量不为1，则会在第一个连接分量遍历完成后终止。如下图4，在B1.C中是无法全部遍历完成的。这个图的文件在G4.TXT，修改表23中第5行，从G4.TXT中读数据，则会发现这个程序仅仅遍历了A、B、C、D，而没有到达过E、F、G这三个顶点。图4两个连同分量的图这个图该如何遍历呢？请同学们自己修改程序，完成这个图的遍历。广度优先遍历到此结束。9/9