图的广度优先遍历ppt课件

1、7.3.2.连通图的广度优先遍历1.广度优先遍历以x开始的连通图访问X，且x入队列若队列不空，重复以下步骤取队头元素并放入v中考察v的各个邻接点，若未访问，则先访问，然后放在队列尾部返回步骤算法描述算法描述:2.算法演示01 v12 v23 V34 V45 v56 v67 v78 v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1v2v3v4v5v6v7v8例图及其邻接表表示演示开始，以v1为遍历的起点01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5队列队列v1访问v101v12v23V34

2、V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v1V1入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v1取队头元素01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v1v2V1的邻接点v2没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v1

3、v2v201v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v1v2v2v3V1的邻接点v3没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v1v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v

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

5、12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v3v4v401v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v3v4v4v5V2的邻接点v5没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1

6、v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v5V3的邻接点v1已经被访问

7、过不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v5v6V3的邻接点v6没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v5v6v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v5v6v6v7V3的邻接点v7没有被访问过，访问

8、之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1

9、v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v4v5v5v6v6v7v7V4的邻接点v2已经被访问过不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v4v5v5v6v6v7v7v8V4的邻接点v8没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2

10、v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v4v5v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v

11、4v5v1队列队列v2v3v4v5v5v6v6v7v7v8v8V5的邻接点v2、v8已经被访问过不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v

12、5v6v6v7v7v8v8V6的邻接点v3、v7已经被访问过不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v7v7v8v8V7的邻接点v3、v6

13、已经被访问过不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v7v8v8V8的邻接点v4、v5已经被访问过不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列队列v2v3v4v5v6v7v8队列为空，算法结束3.算法实现 从演示过程可

14、以看出，我们必须知道顶点是否已经被访问过。在具体实现时，我们用一个数组visited来记录顶点是否被访问过。如果visitedi的值为True，则顶点vi已经被访问，否则没有被访问。3.算法实现Void BFSGraph G，int x）Visited100=False；/假设图中顶点数没有超过100个Visitedx=True；coutx;Queue.push(x);While(!Q.empty()V= Queue.front();Queue.pop();For(v的每个邻接点w）Ifvisitedw=false)Visitedw=True;coutw;Queue.pushw）；当图的存储结构为邻接表时，广度优先算法可以表示如下：void BFS (ALGraph mg,int x)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);练习题：对于下面