最新图的广度优先遍历精品课件.ppt

《最新图的广度优先遍历精品课件.ppt》由会员分享，可在线阅读，更多相关《最新图的广度优先遍历精品课件.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1.广度优先遍历以x开始的连通图访问X，且x入队列若队列不空，重复以下步骤取队头元素并放入v中考察v的各个邻接点，若未访问，则先访问，然后放在队列尾部返回步骤算法描述算法描述:01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v1v2V1的邻接点v2没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v1v2v201v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8

2、v2v8v3v7v3v6v4v5v1队列队列v1v2v2v3V1的邻接点v3没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v1v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v301v12v23V34V45v56v67

3、v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v3V2的邻接点v1已经被访问过不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v3v4V2的邻接点v4没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v

4、7v3v6v4v5v1队列队列v2v2v3v3v4v401v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v3v4v4v5V2的邻接点v5没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v501v12

5、v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v5V3的邻接点v1已经被访问过不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v

6、8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v5v6V3的邻接点v6没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v5v6v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v5v6v6v7V3的邻接点v7没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2

7、v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v4v5v5v

8、6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v4v5v5v6v6v7v7V4的邻接点v2已经被访问过不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v4v5v5v6v6v7v7v8V4的邻接点v8没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v4v

9、5v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v5v6v6v7v7v8v8V5的邻接点v2、v8已经被访问过不

10、再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v6v7v7v8v8V6的邻接点v3、v7已经被访问过不再访问01v12v23V34V45v

11、56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v7v7v8v8V7的邻接点v3、v6已经被访问过不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6

12、v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v7v8v8V8的邻接点v4、v5已经被访问过不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v7v8队列为空，算法结束3.算法实现 从演示过程可以看出，我们必须知道顶点是否已经被访问过。在具体实现时，我们用一个数组visited来记录顶点是否

13、被访问过。如果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

14、)bool visited100=false;queue q;coutmg.vexsx.data 0;w=:NextAdjVex(mg,v,w)if(visitedw=false)coutmg.vexsw.data ;visitedw=true;q.push(w);练习题：对于下面一个图及其存储结构，写出以v2、v8为起始点的广度优先遍历序列。01 v12 v23 V34 V45 v56 v67 v78 v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1v2v3v4v5v6v7v8例图及其邻接表表示答案如下：以v2为起始点：v2-v1-v4-v5-v3-v8-v6-v7以v8为起始点：v8-v4-v5-v2-v1-v3-v6-v7思考题：若图不是连通图，如何进行广度优先遍历？v1v2v3v4v5v6v754 结束语结束语