圖的廣度優(yōu)先遍歷ppt課件

1、7.3.2.連通圖的廣度優(yōu)先遍歷1.廣度優(yōu)先遍歷以x開始的連通圖訪問(wèn)X，且x入隊(duì)列若隊(duì)列不空，重復(fù)以下步驟取隊(duì)頭元素并放入v中考察v的各個(gè)鄰接點(diǎn)，若未訪問(wèn)，則先訪問(wèn)，然后放在隊(duì)列尾部返回步驟算法描述算法描述:2.算法演示01 v12 v23 V34 V45 v56 v67 v78 v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1v2v3v4v5v6v7v8例圖及其鄰接表表示演示開始，以v1為遍歷的起點(diǎn)01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5隊(duì)列隊(duì)列v1訪問(wèn)v101v12v23V34

2、V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v1V1入隊(duì)列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v1取隊(duì)頭元素01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v1v2V1的鄰接點(diǎn)v2沒(méi)有被訪問(wèn)過(guò)，訪問(wèn)之，且入隊(duì)列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v1

3、v2v201v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v1v2v2v3V1的鄰接點(diǎn)v3沒(méi)有被訪問(wèn)過(guò)，訪問(wèn)之，且入隊(duì)列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v1v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v

4、2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v2v3v3V2的鄰接點(diǎn)v1已經(jīng)被訪問(wèn)過(guò)不再訪問(wèn)01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v2v3v3v4V2的鄰接點(diǎn)v4沒(méi)有被訪問(wèn)過(guò)，訪問(wèn)之，且入隊(duì)列01v

5、12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v2v3v3v4v401v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v2v3v3v4v4v5V2的鄰接點(diǎn)v5沒(méi)有被訪問(wèn)過(guò)，訪問(wèn)之，且入隊(duì)列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1

6、v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v3v4v4v5v5V3的鄰接點(diǎn)v1已經(jīng)被訪問(wèn)

7、過(guò)不再訪問(wèn)01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v3v4v4v5v5v6V3的鄰接點(diǎn)v6沒(méi)有被訪問(wèn)過(guò)，訪問(wèn)之，且入隊(duì)列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v3v4v4v5v5v6v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v3v4v4v5v5v6v6v7V3的鄰接點(diǎn)v7沒(méi)有被訪問(wèn)過(guò)，訪問(wèn)

8、之，且入隊(duì)列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1

9、v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v4v4v5v5v6v6v7v7V4的鄰接點(diǎn)v2已經(jīng)被訪問(wèn)過(guò)不再訪問(wèn)01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v4v4v5v5v6v6v7v7v8V4的鄰接點(diǎn)v8沒(méi)有被訪問(wèn)過(guò)，訪問(wèn)之，且入隊(duì)列01v12v23V34V45v56v67v78v8v2

10、v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v4v4v5v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v4v5v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v4v5v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v

11、4v5v1隊(duì)列隊(duì)列v2v3v4v5v5v6v6v7v7v8v8V5的鄰接點(diǎn)v2、v8已經(jīng)被訪問(wèn)過(guò)不再訪問(wèn)01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v4v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v4v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v4v

12、5v6v6v7v7v8v8V6的鄰接點(diǎn)v3、v7已經(jīng)被訪問(wèn)過(guò)不再訪問(wèn)01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v4v5v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v4v5v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v4v5v6v7v7v8v8V7的鄰接點(diǎn)v3、v6

13、已經(jīng)被訪問(wèn)過(guò)不再訪問(wèn)01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v4v5v6v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v4v5v6v7v8v8V8的鄰接點(diǎn)v4、v5已經(jīng)被訪問(wèn)過(guò)不再訪問(wèn)01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列隊(duì)列v2v3v4v5v6v7v8隊(duì)列為空，算法結(jié)束3.算法實(shí)現(xiàn) 從演示過(guò)程可

14、以看出，我們必須知道頂點(diǎn)是否已經(jīng)被訪問(wèn)過(guò)。在具體實(shí)現(xiàn)時(shí)，我們用一個(gè)數(shù)組visited來(lái)記錄頂點(diǎn)是否被訪問(wèn)過(guò)。如果visitedi的值為True，則頂點(diǎn)vi已經(jīng)被訪問(wèn)，否則沒(méi)有被訪問(wèn)。3.算法實(shí)現(xiàn)Void BFSGraph G，int x）Visited100=False；/假設(shè)圖中頂點(diǎn)數(shù)沒(méi)有超過(guò)100個(gè)Visitedx=True；coutx;Queue.push(x);While(!Q.empty()V= Queue.front();Queue.pop();For(v的每個(gè)鄰接點(diǎn)w）Ifvisitedw=false)Visitedw=True;coutw;Queue.pushw）；當(dāng)圖的存儲(chǔ)結(jié)構(gòu)為鄰接表時(shí)，廣度優(yōu)先算法可以表示如下：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);練習(xí)題：對(duì)于下面