橫向優(yōu)先搜尋breadth

8.3橫向優(yōu)先搜尋(breadthfirstsearch)問題：對(duì)於一個(gè)圖G=(V,E)，任給兩個(gè)頂點(diǎn)i,j，試找一條連接頂點(diǎn)i與頂點(diǎn)

j的最短路徑。如果前面有路可以走，記錄所有可以走的路徑，依目前所有可以走的路徑再更進(jìn)一步找所有可以走的路徑，直到找到目的地，不然，找遍所有路徑也找不到目的地。利用橫向優(yōu)先的方式來尋找最短路徑，橫向優(yōu)先的基本精神是：例：一個(gè)簡(jiǎn)單圖如下所示。v0v1v6v3v5v7v2v4v8試找一條連接頂點(diǎn)0與頂點(diǎn)

7的最短路徑。依該圖的adjacencymatrix或adjacencylist由v0

可以走到v1、v2、v3及v6，以圖表示如下：v0v1v6v3v5v7v2v4v8走訪過的頂點(diǎn)以白色顯示，藍(lán)色的點(diǎn)表示已經(jīng)處理完成。以箭頭表示parent與child(先走到與後走到)的關(guān)係。v1無(wú)路可走。v2可以走到v4與v5。

v3可以走到v4

與v7，但v4

已經(jīng)走訪過了。目的地v7

找到了，可以停止搜尋。(v6無(wú)路可走，可以省略不必搜尋。)由目的地v7

沿著箭頭走向v3，再走向v0。<v0，v3，v7>就是一條最短路徑。v0v1v6v3v5v7v2v4v8以程式來處理路徑搜尋的問題，我們需要：一個(gè)adjacencylistL。visit103254768000000000parent103254768-1-1-1-1-1-1-1-1-1q8017263541236004060345246723578243413adjacencylistL

一個(gè)佇列q，每Dequeue

一次，取得一個(gè)頂點(diǎn)v，所有與v相鄰且未走訪的頂點(diǎn)全部Enqueue

到佇列q。一個(gè)陣列visit記錄頂點(diǎn)尚未走訪、走訪過與處理完成的資料，分別以0，1，2表示。一個(gè)陣列parent[k]記錄走訪頂點(diǎn)k之前的位置。例：由下列簡(jiǎn)單圖找一條連接頂點(diǎn)0與頂點(diǎn)7的最短路徑。v0v1v6v3v5v7v2v4v8先將頂點(diǎn)0Enqueue

到佇列q。visit103254768000000000q0parent103254768-1-1-1-1-1-1-1-1-1註明頂點(diǎn)0是已經(jīng)走訪的頂點(diǎn)，即visit[0]=1。1頂點(diǎn)0是起點(diǎn)沒有parent，即parent[0]=-1。由佇列q執(zhí)行Dequeue，取得頂點(diǎn)0，將visit[0]改成2。由adjacencylistL，可以找到頂點(diǎn)1,2,3,6,與頂點(diǎn)0相鄰。visit103254768100000000parent103254768-1-1-1-1-1-1-1-1-18017263541236004060345246723578243413adjacencylistL頂點(diǎn)1,2,3,6,的visit[0]皆為0，即皆未走訪。將頂點(diǎn)1,2,3,6,Enqueue

到佇列上，同時(shí)將visit[]值改成1。並將頂點(diǎn)1,2,3,6,的parent改成0。2q00123611110000由佇列q執(zhí)行Dequeue，取得頂點(diǎn)1，將visit[1]改成2。由adjacencylistL，可以找到頂點(diǎn)0,6,與頂點(diǎn)1相鄰。visit103254768200001111parent103254768-1-1-1-1-100008017263541236004060345246723578243413adjacencylistL頂點(diǎn)0,6,的visit[]值皆不為0，即已走訪。q123612由佇列q執(zhí)行Dequeue，取得頂點(diǎn)2，將visit[2]改成2。由adjacencylistL，可以找到頂點(diǎn)0,3,4,5與頂點(diǎn)2相鄰。visit103254768200002111parent103254768-1-1-1-1-100008017263541236004060345246723578243413adjacencylistL頂點(diǎn)0,3,的visit[]值皆不為0。頂點(diǎn)4,5的visit[]值皆為0，即未走訪。q23622將頂點(diǎn)4,5Enqueue

到佇列上，同時(shí)將visit[]值改成1。並將頂點(diǎn)4,5的parent改成2。411225由佇列q執(zhí)行Dequeue，取得頂點(diǎn)3，將visit[3]改成2。由adjacencylistL，可以找到頂點(diǎn)0,2,4,6,7與頂點(diǎn)3相鄰。visit103254768211002121parent103254768-122-1-100008017263541236004060345246723578243413adjacencylistL頂點(diǎn)0,2,4,6的visit[]值皆不為0。頂點(diǎn)7的visit[7]值皆為0，即未走訪。2將頂點(diǎn)7Enqueue

到佇列上，同時(shí)將visit[7]值改成1。並將頂點(diǎn)7的parent改成3。頂點(diǎn)7為目的地，搜尋至此結(jié)束。13q364537visit103254768211012221parent103254768-122-1300008017263541236004060345246723578243413adjacencylistL頂點(diǎn)7為目的地，由陣列parent可以追查出最短路徑。q6457頂點(diǎn)7的parent是3。頂點(diǎn)3的parent是0。頂點(diǎn)0的parent是-1。由此可得最短路徑是<0,3,7>。scanf(“%d%d”,&i,&j);foundGoal=FALSE;Enqueue(i);visit[i]=1;while(!foundGoal){

if(isQueueEmpty())break;current=Dequeue();

currNode=L[current];

while(currNode!=NULL){k=currNode->vertex;

if(visit[k]==0){

Enqueue(k);

visit[k]=1;parent[k]=current;