《图的广度优先遍历》由会员分享，可在线阅读，更多相关《图的广度优先遍历（53页珍藏版）》请在金锄头文库上搜索。
1、7.3.2.连通图的广度优先遍历1.广度优先遍历以x开始的连通图访问X，且x入队列 若队列不空，重复以下步骤 取队头元素并放入v中 考察v的各个邻接点，若未访 问，则先访问，然后放在队列 尾部 返回步骤算法描述:2.算法演示01 v12 v23 V34 V45 v56 v67 v78 v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1v2v3v4v5v6v7v8例图及其邻接表表示演示开始，以v1为遍历的起点01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5队列v1 访问v101v12v23V3
2、4V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v1V1入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v1取队头元素01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v1v2V1的邻接点v2没 有被访问过，访 问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v1v2v20
3、1v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v1v2v2v3V1的邻接点v3没 有被访问过，访 问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v1v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3
4、v6v4v5v1队列v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v2v3v3V2的邻接点v1已 经被访问过不再 访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v2v3v3v4V2的邻接点v4没 有被访问过，访 问之，且入队列01v12v23V34V45v5
5、6v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v2v3v3v4v401v12v23V34V45v56v67v78v8v2v3v1v4 v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v2v3v3v4v4v5V2的邻接点v5没 有被访问过，访 问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7
6、v3v6v4v5v1队列v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v3v4v4v5v5V3的邻接点v1已 经被访问过不再 访问01v12v23V34V45v56
7、v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v3v4v4v5v5v6V3的邻接点v6没 有被访问过，访 问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v3v4v4v5v5v6v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6 v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v3v4v4v5v5v6v6v7V3的邻接点v7没 有被访问过，访 问之，且入队列01v12v23V34V45v56
8、v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v
9、5v1队列v2v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v4v5v5v6v6v7v7V4的邻接点v2已 经被访问过不再 访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v4v5v5v6v6v7v7v8V4的邻接点v8没 有被访问过，访 问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v
10、4v5v1队列v2v3v4v4v5v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v5v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v5v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v5v5v6v6v7v7v8v8V5的邻接点v2
11、、 v8已经被访问过 不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v5v6v6v7v7v8v8V6的邻接点v3、 v7已经被访问过 不再访问01v12v2
12、3V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v5v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v5v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v5v6v7v7v8v8V7的邻接点v3、 v6已经被访问过 不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5
13、v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v5v6v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v5v6v7v8v8V8的邻接点v4、 v5已经被访问过 不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v5v6v7v8队列为空，算法结束3.算法实现从演示过程可以看出，我们必须知道顶点 是否已经被访问过。在具体实现时，我们 用一个数组visited来记录顶点是
14、否被访问 过。如果visitedi的值为True，则顶点vi已 经被访问，否则没有被访问。3.算法实现Void BFS（Graph G，int x） Visited100=False；/假设图中顶点数没有超过100个 Visitedx=True；cout q; cout0;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思考题：若图不是连通图，如何进行广度优先遍历？v1v2v3v4v5v6v7
