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

西北师范大学地环学院地理信息系 数据结构实验讲义 十一 图的广度优先遍历 张长城 2011-2-8 [图存储以及深度优先遍历算法分析，C语言实现] 实验任务描述 1 分析广度优先遍历算法； 2 用C语言实现图的广度优先遍历。 邻接矩阵存储图的广度优先遍历过程分析 对图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 对广度优先遍历，还需要补充一个队列、来记录一个顶点可以抵达到的其他顶点。 广度优先遍历过程如下： 图 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个函数，于是有以下队列定义：  1 2 3 4 5 struct Queue { struct LinkedList * LinkQueue; int Count; }; 表3 为广度优先遍历图准备队列 见B0.c 由于我们已经确定使用链表做队列，所以队列实际就是链表的换名包装，所以我们可以理解为队列就是链表的另一种应用，表3的程序就是这样的做法，所以对队列的初始化，就是： 1 2 3 4 5 6 7 8 struct Queue * QueueInit() { struct Queue *q; q=(struct Queue *)malloc(sizeof(struct Queue)); q-LinkQueue=LinkedListInit(); q-Count=0; return q; } 表4 队列初始化函数 见B0.c 有了队列的初始化，则进入队列、实际相当于给这个链表追加一条记录，就是Append()的另类包装： 1 2 3 4 5 6 7 8 int EnQueue(struct Queue *Q,struct ElemType *E) { if(Q==NULL) return -1; if(E==NULL) return -2; Append(Q-LinkQueue,E); Q-Count++; return 0; } 表5 数据E进入队列，见B0.c 注意数据出队列，出队列总是把链表中第一个结点的数据给出来、并删除第一个结点，所以出队列就是： 1 2 3 4 5 6 7 8 9 10 11 int DeQueue(struct Queue *Q,struct ElemType *E) { struct ElemType *pE; if(Q==NULL) return -1; if(E==NULL) return -2; pE=LinkedListGet(Q-LinkQueue,1); ElemCopy(pE,E); LinkedListDel(Q-LinkQueue,