图的广度优先遍历

7.3.2.连通图的广度优先遍历1.广度优先遍历以x开始的连通图①访问X，且x入队列②若队列不空，重复以下步骤③取队头元素并放入v中④考察v的各个邻接点，若未访问，则先访问，然后放在队列尾部⑤返回步骤②算法描述:2.算法演示01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1v2v3v4v5v6v7v8例图及其邻接表表示演示开始，以v1为遍历的起点01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5队列v1访问v101v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v1V1入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v1取队头元素01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v1v2V1的邻接点v2没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v1v2v201v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v1v2v2v3V1的邻接点v3没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v1v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v2v3v3V2的邻接点v1已经被访问过不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v2v3v3v4V2的邻接点v4没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v2v3v3v4v401v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v2v3v3v4v4v5V2的邻接点v5没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v3v4v4v5v5V3的邻接点v1已经被访问过不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v3v4v4v5v5v6V3的邻接点v6没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v3v4v4v5v5v6v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v3v4v4v5v5v6v6v7V3的邻接点v7没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v4v5v5v6v6v7v7V4的邻接点v2已经被访问过不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v4v5v5v6v6v7v7v8V4的邻接点v8没有被访问过，访问之，且入队列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v4v5v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v5v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v5v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v5v5v6v6v7v7v8v8V5的邻接点v2、v8已经被访问过不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v5v6v6v7v7v8v8V6的邻接点v3、v7已经被访问过不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v5v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v5v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v5v6v7v7v8v8V7的邻接点v3、v6已经被访问过不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v5v6v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v5v6v7v8v8V8的邻接点v4、v5已经被访问过不再访问01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1队列v2v3v4v5v6v7v8队列为空，算法结束3.算法实现从演示过程可以看出，我们必须知道顶点是否已经被访问过。在具体实现时，我们用一个数组visited[]来记录顶点是否被访问过。如果visited[i]的值为True，则顶点vi已经被访问，否则没有被访问。3.算法实现VoidBFS（GraphG，intx）{Visited[100]={False}；//假设图中顶点数没有超过100个Visited[x]=True；coutx;Queue.push(x);While(!Q.empty()){V=Queue.front();Queue.pop();For(v的每个邻接点w）If（visited[w]==false){Visited[w]=True;coutw;Queue.push（w）；}}}当图的存储结构为邻接表时，广度优先算法可以表示如下：voidBFS(ALGraphmg,intx){boolvisited[100]={false};queueintq;coutmg.vexs[x].data;visited[x]=true;q.push(x);while(q.empty()==false){intv=q.front();q.pop();for(intw=::FirstAdjVex(mg,v);w0;w=::NextAdjVex(mg,v,w)){if(visited[w]==false){coutmg.vexs[w].data;visited[w]=true;q.push(w);}}}}练习题：对于下面一个图及其存储结构，写出以v2、v8为起始点的广度优先遍历序列。01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1v2v3v4v5v6v7v8例图及其邻接表表示答案如下：以v2为起始点：v2-v1-v4-v5-v3-v8-v6-v7以v8为起始点：v8-v4-v5-v2-v1-v3-v6-v7思考题：若图不是连通图，如何进行广度优先遍历？v1v2v3v4v5v6v7