第7章 图 7.4 广度优先搜索遍历《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

第7章 图 7.1 图的基本概念 7.2 图的存贮结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径 7.3.2 广度优先搜索遍历 广度优先搜索遍历类似于树的按层次遍历。设图G的初态是所有顶点均未访问，在G中任选一顶点i作为初始点，则广度优先搜索的基本思想是： (1)    首先访问顶点i，并将其访问标志置为已被访问，即visited[i]=1； (2)    接着依次访问与顶点i有边相连的所有顶点W1，W2，…，Wt； (3)    然后再按顺序访问与W1，W2，…，Wt有边相连又未曾访问过的顶点； 依此类推，直到图中所有顶点都被访问完为止 。 1． 广度优先搜索的思想 例如，对图7-13所示无向图G7，从顶点1出发的广度优先搜索遍历序列可有多种，下面仅给出三种，其它可作类似分析。 在无向图G7中，从顶点1出发的广度优先搜索遍历序列举三种为： 1, 2, 3, 4, 5, 6, 7, 8 1, 3, 2, 7, 6, 5, 4, 8 1, 2, 3, 5, 4, 7, 6, 8 和深度优先搜索类似，在遍历的过程中也需要一个访问标志数组。并且，为了顺次访问路径长度为2、3、…的顶点，需附设队列以存储已被访问的路径长度为1，2，…的顶点。 广 度优先遍历的算法如下所示。 void bfs(Graph g ,vtx * v） { SETNULL(Q); visit(v); visited[v]=1; ENQUEUE(Q,v); //已访问过的顶点入队 while (!EMPTY(Q)) { v=DEQUEUE(Q); //队头元素v出队 w=FIRSTADJ(g,v);//求v的邻接点 while (w!=0) { if (!visited[w]) { visit(w); visited[w]=1; ENQUEUE(Q,w); } w=NEXTADJ(g,v,w);//求w后面的v的下一邻接点 } } }//bfs 例: 用邻接矩阵实现图的广度优先搜索遍历 0 1 1 1 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 1 1 0 图 7 - 14 无向图 G 7 的邻接矩阵 根据该算法用及图7-14中的邻接矩阵，可以得到图7-13的无向图G7的广度优先搜索序列，若从顶点1出发，广度优先搜索序列为：1，2，3， 4，5， 6，7，8。若从顶点3出发，广度优先搜索序列为：3， 1， 6， 7， 2， 8， 4， 5，从其它点出发的广度优先搜索序列可根据同样类似方法分析。 算法描述如下： void bfs( int k) //从顶点V k+1出发广度优先搜索图g，图g用邻接矩阵表示，visited为访问标志向量 { int i, j ; SETNULL(Q); //设置空队列Q printf(“%c”, g.vexs[k]); // 访问出发点V k+1 visited[k]=1 ; //标记置1表示已经访问 ENQUEUE(Q, K) ; //已访问过的顶点入队列 while (!EMPTY(Q)) { i=DEQUEUE(Q) ; //队头元素出队列 for (j=0; j<n; j++) if ((g.arcs[i][j]==1)&&(!visited[j])) { printf(“%c”, g.vexs[j]); vsited[j]=1 ; ENQUEUE(Q, j); } } } （2）用邻接表实现图的广序优先搜索遍历 仍以无向图G7及图7-16所示邻接表来说明邻接表上实现广度优先搜索遍历的过程 根据该算法及图7-16，可以得到图G7的广度优先搜索序列，若从顶点1出发，广度优先搜索序列为：1，2，3，4，5，6，7，8，若从顶点7出发，广度优先搜索序列为：7，3，8，1，6，4，5，2，从其它顶点出发的广度优先搜索序列可根据同样类似方法分析。 void bfsl (int k) //从V k+1出发深度优先搜索图gl，gl用邻接表表示 { int i; ed