图的广度优先遍历.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为起始点的广度优先遍历序列。,例图及其邻接表表示,答案如下：以v2为起始点：v2-v1-v4-v5-v3-v8-v6-v7以v8为起始点：v8-v4-v5-v2-v1-v3-v6-v7,思考题：,若图不是连通图，如何进行广度优先遍历？,v1,v2,v3,v4,v5,v6,v7,
