图的广度优先遍历.ppt

7.3.2.连通图的广度优先遍历,1.广度优先遍历以x开始的连通图,访问X，且x入队列 若队列不空，重复以下步骤 取队头元素并放入v中 考察v的各个邻接点，若未访问，则先访问，然后放在队列尾部 返回步骤,算法描述:,2.算法演示,例图及其邻接表表示,演示开始，以v1为遍历的起点,队列,v1,访问v1,v1,队列,v1,V1入队列,v1,队列,v1,取队头元素,v1,队列,v1,v2,V1的邻接点v2没有被访问过，访问之，且入队列,v1,队列,v1,v2,v2,v1,队列,v1,v2,v2,v3,V1的邻接点v3没有被访问过，访问之，且入队列,v1,队列,v1,v2,v2,v3,v3,v1,队列,v2,v2,v3,v3,v1,队列,v2,v2,v3,v3,v1,队列,v2,v2,v3,v3,v1,队列,v2,v2,v3,v3,V2的邻接点v1已经被访问过不再访问,v1,队列,v2,v2,v3,v3,v4,V2的邻接点v4没有被访问过，访问之，且入队列,v1,队列,v2,v2,v3,v3,v4,v4,v1,队列,v2,v2,v3,v3,v4,v4,v5,V2的邻接点v5没有被访问过，访问之，且入队列,v1,队列,v2,v2,v3,v3,v4,v4,v5,v5,v1,队列,v2,v3,v3,v4,v4,v5,v5,v1,队列,v2,v3,v3,v4,v4,v5,v5,v1,队列,v2,v3,v3,v4,v4,v5,v5,v1,队列,v2,v3,v3,v4,v4,v5,v5,V3的邻接点v1已经被访问过不再访问,v1,队列,v2,v3,v3,v4,v4,v5,v5,v6,V3的邻接点v6没有被访问过，访问之，且入队列,v1,队列,v2,v3,v3,v4,v4,v5,v5,v6,v6,v1,队列,v2,v3,v3,v4,v4,v5,v5,v6,v6,v7,V3的邻接点v7没有被访问过，访问之，且入队列,v1,队列,v2,v3,v3,v4,v4,v5,v5,v6,v6,v7,v7,v1,队列,v2,v3,v4,v4,v5,v5,v6,v6,v7,v7,v1,队列,v2,v3,v4,v4,v5,v5,v6,v6,v7,v7,v1,队列,v2,v3,v4,v4,v5,v5,v6,v6,v7,v7,v1,队列,v2,v3,v4,v4,v5,v5,v6,v6,v7,v7,V4的邻接点v2已经被访问过不再访问,v1,队列,v2,v3,v4,v4,v5,v5,v6,v6,v7,v7,v8,V4的邻接点v8没有被访问过，访问之，且入队列,v1,队列,v2,v3,v4,v4,v5,v5,v6,v6,v7,v7,v8,v8,v1,队列,v2,v3,v4,v5,v5,v6,v6,v7,v7,v8,v8,v1,队列,v2,v3,v4,v5,v5,v6,v6,v7,v7,v8,v8,v1,队列,v2,v3,v4,v5,v5,v6,v6,v7,v7,v8,v8,V5的邻接点v2、v8已经被访问过不再访问,v1,队列,v2,v3,v4,v5,v6,v6,v7,v7,v8,v8,v1,队列,v2,v3,v4,v5,v6,v6,v7,v7,v8,v8,v1,队列,v2,v3,v4,v5,v6,v6,v7,v7,v8,v8,V6的邻接点v3、v7已经被访问过不再访问,v1,队列,v2,v3,v4,v5,v6,v7,v7,v8,v8,v1,队列,v2,v3,v4,v5,v6,v7,v7,v8,v8,v1,队列,v2,v3,v4,v5,v6,v7,v7,v8,v8,V7的邻接点v3、v6已经被访问过不再访问,v1,队列,v2,v3,v4,v5,v6,v7,v8,v8,v1,队列,v2,v3,v4,v5,v6,v7,v8,v8,V8的邻接点v4、v5已经被访问过不再访问,v1,队列,v2,v3,v4,v5,v6,v7,v8,队列为空，算法结束,3.算法实现,从演示过程可以看出，我们必须知道顶点是否已经被访问过。在具体实现时，我们用一个数组visited来记录顶点是否被访问过。如果visitedi的值为True，则顶点vi已经被访问，否则没有被访问。,3.算法实现,Void BFS（Graph G，int x） Visited100=False；/假设图中顶点数没有超过100个 Visitedx=True；coutx;Queue.push(x); While(!Q.empty() V= Queue.front(); Queue.pop(); For(v的每个邻接点w） If（visitedw=false) Visitedw=True;coutw;Queue.push（w）； ,当图的存储结构为邻接表时，广度优先算法可以表示如下： void BFS (ALGraph mg,int x) bool visited100=false; queue q; cout0;w=:NextAdjVex(mg,v,w) if(visitedw=false) coutmg.vexsw.data“ “; visitedw=true; q.push(w); ,练习题： 对于下面一个图及其存储结构，写出以v2、v8为起始点的广度优先遍历序列。,例图及其邻接表表示,答案