《图的广度优先遍历课件》由会员分享，可在线阅读，更多相关《图的广度优先遍历课件（53页珍藏版）》请在金锄头文库上搜索。
1、7.3.2.连通图的广度优先遍历图的广度优先遍历课件1.广度优先遍历以x开始的连通图访问X，且x入队列若队列不空，重复以下步骤取队头元素并放入v中考察v的各个邻接点，若未访问，则先访问，然后放在队列尾部返回步骤算法描述算法描述:图的广度优先遍历课件2.算法演示图的广度优先遍历课件01 v12 v23 V34 V45 v56 v67 v78 v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1v2v3v4v5v6v7v8例图及其邻接表表示图的广度优先遍历课件演示开始，以v1为遍历的起点图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v
2、4v5v1v6v7v2v8v2v8v3v7v3v6v4v5队列队列v1访问v1图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v1V1入队列图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v1取队头元素图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v1v2V1的邻接点v2没有被访
3、问过，访问之，且入队列图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v1v2v2图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v1v2v2v3V1的邻接点v3没有被访问过，访问之，且入队列图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v1v2v2v3v3图的广度优先遍历课件0
4、1v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v3图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v3图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v3图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v
5、2v8v3v7v3v6v4v5v1队列队列v2v2v3v3V2的邻接点v1已经被访问过不再访问图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v3v4V2的邻接点v4没有被访问过，访问之，且入队列图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v3v4v4图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v
6、8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v3v4v4v5V2的邻接点v5没有被访问过，访问之，且入队列图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v3v4v4v5v5图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v5图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v
7、2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v5图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v5图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v5V3的邻接点v1已经被访问过不再访问图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3
8、v6v4v5v1队列队列v2v3v3v4v4v5v5v6V3的邻接点v6没有被访问过，访问之，且入队列图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v5v6v6图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v5v6v6v7V3的邻接点v7没有被访问过，访问之，且入队列图的广度优先遍历课件01v12v23V34V45v56v67v78v
9、8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v5v6v6v7v7图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v4v5v5v6v6v7v7图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v4v5v5v6v6v7v7图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1
10、v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v4v5v5v6v6v7v7图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v4v5v5v6v6v7v7V4的邻接点v2已经被访问过不再访问图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v4v5v5v6v6v7v7v8V4的邻接点v8没有被访问过，访问之，且入队列图的广度优先遍
11、历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v4v5v5v6v6v7v7v8v8图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v5v6v6v7v7v8v8图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v5v6v6v7v7v8v8图的广度优先遍历
12、课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v5v6v6v7v7v8v8V5的邻接点v2、v8已经被访问过不再访问图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v6v7v7v8v8图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v6v7
13、v7v8v8图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v6v7v7v8v8V6的邻接点v3、v7已经被访问过不再访问图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v7v7v8v8图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3
14、v4v5v6v7v7v8v8图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v7v7v8v8V7的邻接点v3、v6已经被访问过不再访问图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v7v8v8图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列
15、v2v3v4v5v6v7v8v8V8的邻接点v4、v5已经被访问过不再访问图的广度优先遍历课件01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v7v8队列为空，算法结束图的广度优先遍历课件3.算法实现 从演示过程可以看出，我们必须知道顶点是否已经被访问过。在具体实现时，我们用一个数组visited来记录顶点是否被访问过。如果visitedi的值为True，则顶点vi已经被访问，否则没有被访问。图的广度优先遍历课件3.算法实现Void BFS（Graph G，int x）Visited100
16、=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;coutmg.vexsx.data 0;w=:NextAdjVex(mg,v,w
17、)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图的广度优先遍历课件思考题：若图不是连通图，如何进行广度优先遍历？v1v2v3v4v5v6v7图的广度优先遍历课件
