圖的遍歷深度優(yōu)先遍歷和廣度優(yōu)先遍歷

圖的遍歷深度優(yōu)先遍歷和廣度優(yōu)先遍歷第1頁(yè)，共44頁(yè)，2023年，2月20日，星期六20、圖的遍歷深度優(yōu)先遍歷和廣度優(yōu)先遍歷

掌握?qǐng)D的深度優(yōu)先和廣度優(yōu)先遍歷的性質(zhì)和方法，以及基于鄰接矩陣和鄰接表存儲(chǔ)結(jié)構(gòu)的遞歸和非遞歸的算法實(shí)現(xiàn)第2頁(yè)，共44頁(yè)，2023年，2月20日，星期六目錄20.1概述20.2深度優(yōu)先遍歷

20.3深度優(yōu)先遍歷的性質(zhì)20.4廣度優(yōu)先遍歷20.5廣度優(yōu)先遍歷的性質(zhì)第3頁(yè)，共44頁(yè)，2023年，2月20日，星期六20、圖的遍歷

從這節(jié)起，我們介紹圖的一些重要操作的實(shí)現(xiàn)，包括遍歷、拓?fù)渑判?、關(guān)鍵路徑等。另有一些重要操作，如最短路徑問(wèn)題、最小生成樹(shù)問(wèn)題，由于主要難點(diǎn)在于算法，所以我們安排在后面的算法設(shè)計(jì)章節(jié)中介紹。圖的遍歷與樹(shù)的遍歷一樣具有十分重要的作用，圖的許多其他操作（算法）都與遍歷相關(guān)。第4頁(yè)，共44頁(yè)，2023年，2月20日，星期六20.1概述

圖的遍歷的含意是，從圖中某結(jié)點(diǎn)出發(fā)，按某既定方式訪問(wèn)圖中各個(gè)可訪問(wèn)到的結(jié)點(diǎn)，使每個(gè)可訪問(wèn)到的結(jié)點(diǎn)恰被訪問(wèn)一次。

圖的遍歷方式有兩種：深度優(yōu)先與廣度優(yōu)先方式，分別對(duì)應(yīng)于樹(shù)的先根遍歷與層序遍歷。樹(shù)中不存在回路，但圖中可能有回路。因此，當(dāng)沿回路進(jìn)行掃描時(shí)，一個(gè)結(jié)點(diǎn)可能被掃描到多次，可能導(dǎo)致死循環(huán)。為了避免這種情形，在遍歷中，應(yīng)為每個(gè)結(jié)點(diǎn)設(shè)立一個(gè)訪問(wèn)標(biāo)志，每掃描到一個(gè)結(jié)點(diǎn)，要檢查它的訪問(wèn)標(biāo)志，若標(biāo)志為“未訪問(wèn)”，則按正常方式對(duì)其進(jìn)行處理（如訪問(wèn)或轉(zhuǎn)到它的鄰接點(diǎn)等），否則放過(guò)它，掃描下一個(gè)結(jié)點(diǎn)。第5頁(yè)，共44頁(yè)，2023年，2月20日，星期六

訪問(wèn)標(biāo)志的設(shè)置有兩種方法：①在描述圖結(jié)的記錄中增設(shè)一個(gè)訪問(wèn)標(biāo)志位。這種方法的優(yōu)點(diǎn)是，訪問(wèn)“訪問(wèn)標(biāo)志”的方法與訪問(wèn)結(jié)點(diǎn)的方法一致。如果訪問(wèn)標(biāo)志需要與圖結(jié)構(gòu)同生命期，則這種方法比較合適。但是，若訪問(wèn)標(biāo)志要重復(fù)使用，就必須先重新初始化訪問(wèn)標(biāo)志。如果圖結(jié)點(diǎn)的存儲(chǔ)不利于順序訪問(wèn)，這往往也是個(gè)遍歷問(wèn)題！②另設(shè)一個(gè)“訪問(wèn)數(shù)組”，令它的每個(gè)元素對(duì)應(yīng)于一個(gè)圖結(jié)點(diǎn)訪問(wèn)標(biāo)志。這種方法的訪問(wèn)標(biāo)志很容易多次初始化。第6頁(yè)，共44頁(yè)，2023年，2月20日，星期六從圖中某一結(jié)點(diǎn)出發(fā)，一趟只能遍歷到它所在的極大連通分量中的結(jié)點(diǎn)，要想遍歷到圖中各結(jié)點(diǎn)，需進(jìn)行多趟遍歷（每趟遍歷一個(gè)極大連通分量）。該過(guò)程可描述為：

for(圖中每個(gè)結(jié)點(diǎn)v)if(v尚未被訪問(wèn)過(guò))

從v出發(fā)遍歷該圖;

下面只考慮從一點(diǎn)出發(fā)遍歷，因此有可能會(huì)出現(xiàn)遍歷不到的點(diǎn)。即那些初始點(diǎn)無(wú)路徑可達(dá)的點(diǎn)，是遍歷不到的。第7頁(yè)，共44頁(yè)，2023年，2月20日，星期六20.2深度優(yōu)先遍歷

(一)遍歷規(guī)則從圖中某結(jié)點(diǎn)v0出發(fā)，深度優(yōu)先遍歷（DFS:DepthFirstSearch）圖的規(guī)則為：

·訪問(wèn)v0；

·對(duì)v0的各個(gè)出點(diǎn)v01，v02，…，v0m，每次從它們中按一定方式（也可任選）選取一個(gè)未被訪問(wèn)過(guò)的結(jié)點(diǎn)，從該結(jié)點(diǎn)出發(fā)按深度優(yōu)先遍歷方式遍歷。

顯然，因?yàn)槲覀儧](méi)有規(guī)定對(duì)出點(diǎn)的遍歷次序，所以，圖的深度優(yōu)先遍歷結(jié)果一般不唯一。

第8頁(yè)，共44頁(yè)，2023年，2月20日，星期六

例如，對(duì)圖

20?1給出的有向圖與無(wú)向圖，一些遍歷結(jié)果（結(jié)點(diǎn)訪問(wèn)次序）為：左圖：從1出發(fā)：1，2，4，5；或1，5，2，4

從2出發(fā)：2，1，5，4；或2，4，1，5

右圖：從a出發(fā)：a，b，c，d；或a，b，d，c;…

…

12543abcd圖20?1一個(gè)有向圖（左）和無(wú)向圖第9頁(yè)，共44頁(yè)，2023年，2月20日，星期六1.一般算法

下面考慮深度優(yōu)先遍歷的遞歸實(shí)現(xiàn)的一般方法（存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)）。圖的深度優(yōu)先遍歷與二叉樹(shù)的前序遍歷相似。不同之處有：①二叉樹(shù)每個(gè)結(jié)點(diǎn)至多有兩個(gè)可達(dá)鄰接點(diǎn)（左右兒子），而圖的可達(dá)鄰接點(diǎn)數(shù)目不定；②對(duì)二叉樹(shù)，沿可達(dá)鄰接點(diǎn)搜索時(shí)不會(huì)發(fā)生回繞，但對(duì)圖，若不加特別控制，就有可能回繞。下面是圖的深度優(yōu)先遍歷遞歸算法的一般性描述。如果要另設(shè)一個(gè)數(shù)組作為訪問(wèn)標(biāo)志，則該數(shù)組要在遞歸過(guò)程（函數(shù)）之外初始化為“未訪問(wèn)”。

（二）遞歸實(shí)現(xiàn)方法第10頁(yè)，共44頁(yè)，2023年，2月20日，星期六longDFS(圖g，結(jié)點(diǎn)v0){//圖深度優(yōu)先遍歷遞歸算法。從結(jié)點(diǎn)v0出發(fā)，深度優(yōu)先遍歷圖g，返回訪問(wèn)到的結(jié)點(diǎn)總數(shù)

intnNodes;//寄存訪問(wèn)到的結(jié)點(diǎn)數(shù)目

訪問(wèn)v0;

為v0置已訪問(wèn)標(biāo)志;nNodes=1;

求出v0的第1個(gè)可達(dá)鄰接點(diǎn)v;while(v存在){if(v未被訪問(wèn)過(guò))nNodes=nNodes+DFS(g,v);

求出v0的下個(gè)可達(dá)鄰接點(diǎn)v;}returnnNodes;}

第11頁(yè)，共44頁(yè)，2023年，2月20日，星期六12543

12345

101001210010300001410000500000所示圖的鄰接矩陣g112130415

1

圖20?1有向圖訪問(wèn)標(biāo)識(shí)數(shù)組visited1245輸出數(shù)組resu例如從1點(diǎn)深度優(yōu)先遍歷，先把1設(shè)置訪問(wèn)標(biāo)志，并置入輸出數(shù)組resu，然后從鄰接矩陣的第一行，掃描各列，找到最近的鄰接點(diǎn)2，將其設(shè)置訪問(wèn)標(biāo)志，并進(jìn)入輸出數(shù)組，接著從鄰接矩陣的2行掃描，找到第一個(gè)構(gòu)成邊的點(diǎn)是1，檢查訪問(wèn)標(biāo)識(shí)數(shù)組，發(fā)現(xiàn)1已經(jīng)訪問(wèn)過(guò)，跳過(guò)，找第二個(gè)構(gòu)成邊的點(diǎn)4，設(shè)置訪問(wèn)標(biāo)識(shí)，進(jìn)入輸出數(shù)組，再?gòu)泥徑泳仃嚨牡?行掃描，尋找構(gòu)成邊的點(diǎn)，除1外在無(wú)其他點(diǎn)，返回2行，繼續(xù)尋找，也無(wú)新點(diǎn)，返回1，找到5，將5置訪問(wèn)標(biāo)志，進(jìn)入輸出數(shù)組，1行再無(wú)其他新點(diǎn)，遍歷結(jié)束，返回遍歷元素個(gè)數(shù)為4。第12頁(yè)，共44頁(yè)，2023年，2月20日，星期六

2．鄰接矩陣實(shí)現(xiàn)

這里我們?yōu)榱送怀鲋黝}、簡(jiǎn)化問(wèn)題，假定圖是用一般的鄰接矩陣存儲(chǔ)，鄰接矩陣用簡(jiǎn)單的二維數(shù)組表示（靜態(tài)），用0和1分別表示無(wú)邊和有邊。圖結(jié)點(diǎn)用自然數(shù)編號(hào)。

longDFS1(intg[][CNST_NumNodes],longn,longv0,char*visited,long*resu，long&top){//深度優(yōu)先遍歷圖（遞歸）。圖g為鄰接矩陣，結(jié)點(diǎn)編號(hào)為

0~n.返回實(shí)際遍歷到的結(jié)點(diǎn)數(shù)目

//visited是訪問(wèn)標(biāo)志數(shù)組，調(diào)用本函數(shù)前，應(yīng)為其分配空間并初始化為全0(未訪問(wèn))//resu為一維數(shù)組，用于存放所遍歷到的結(jié)點(diǎn)的編號(hào)，調(diào)用本函數(shù)前，應(yīng)為其分配空間第13頁(yè)，共44頁(yè)，2023年，2月20日，星期六

longnNodes,i;

nNodes=1;resu[top++]=v0;//將訪問(wèn)到的結(jié)點(diǎn)依次存于resu[]visited[v0]=1;//為v0置已訪問(wèn)標(biāo)志

for(i=0;i<n;i++){//依次從v0的各個(gè)出點(diǎn)出發(fā)，深度優(yōu)先遍歷圖

if(g[v0][i]!=0)//若<v0,i>是邊

if(!visited[i])//若結(jié)點(diǎn)i未被訪問(wèn)過(guò)

nNodes=nNodes+DFS1(g,n,i,visited,resu);//從i起深度優(yōu)先遍歷圖

}returnnNodes;}

第14頁(yè)，共44頁(yè)，2023年，2月20日，星期六

A

如果不想讓visited或top做為函數(shù)參數(shù)，也可以在函數(shù)中將其定義為static型量。但是，這樣的程序是不可再入的，即函數(shù)再次被調(diào)用時(shí)，static型的量也不重新初始化，造成錯(cuò)誤！

上面函數(shù)中的參數(shù)visited和top實(shí)質(zhì)上是中間變量，只是為了避免在遞歸調(diào)用時(shí)重新初始化而放在參數(shù)表中，造成使用的不方便，為此，做個(gè)包裝程序：

longDFS1(intg[][CNST_NumNodes],longn,longv0,long*resu){char*visited;longtop=0;visited=newchar[n];for(longi=0;i<n;i++)visited[i]=0;longnum=DFS1(g,n,v0,visited,resu,top);deletevisited;returnnum;}第15頁(yè)，共44頁(yè)，2023年，2月20日，星期六1254312452b5^1d4^5^1^a1c2e3f4^5對(duì)應(yīng)的鄰接表圖20?2有向圖1121304151訪問(wèn)標(biāo)識(shí)數(shù)組visited輸出數(shù)組resu地址起終權(quán)信息鏈a12bb15∧c21dd24∧e35∧f41∧

鄰接表邊PNodes[]

終點(diǎn)2作為下次的始點(diǎn)，由于1點(diǎn)已訪問(wèn)過(guò)，跳過(guò)，找到4，記標(biāo)識(shí)，送輸出，4有作為新的始點(diǎn)重復(fù)上述過(guò)程第16頁(yè)，共44頁(yè)，2023年，2月20日，星期六

3．鄰接表深度優(yōu)先遍歷的實(shí)現(xiàn)

template<classTElem,classTEdgeElem>longDFS2(TGraphNodeAL<TElem,TEdgeElem>*nodes,longn,longv0,char*visited,long*resu,long&top){//深度優(yōu)先遍歷用鄰接表表示的圖。nodes是鄰接表的頭數(shù)組，n為結(jié)點(diǎn)個(gè)數(shù)（編號(hào)為0~n）。

//v0為遍歷的起點(diǎn)。返回實(shí)際遍歷到的結(jié)點(diǎn)的數(shù)目。

//visited是訪問(wèn)標(biāo)志數(shù)組，調(diào)用本函數(shù)前，應(yīng)為其分配空間并初始化為全0(未訪問(wèn))//resu為一維數(shù)組，用于存放所遍歷到的結(jié)點(diǎn)的編號(hào)，調(diào)用本函數(shù)前，應(yīng)為其分配空間

longnNodes,i;TGraphEdgeAL<TEdgeElem>*p;

nNodes=1;

第17頁(yè)，共44頁(yè)，2023年，2月20日，星期六

resu[top++]=v0;//將訪問(wèn)到的結(jié)點(diǎn)依次存于resu[]

visited[v0]=1;//置v0為“已訪問(wèn)”標(biāo)志

p=nodes[v0].firstOutEdge;//求出v0的第一個(gè)出點(diǎn)p

while(p!=NULL){if(!visited[p->endNo])//若p未訪問(wèn)，則從p出發(fā)深度優(yōu)先遍歷

nNodes=nNodes+DFS2(nodes,n,p->endNo,visited,resu,top);p=p->next;//令p指向v0的下個(gè)出點(diǎn)

}returnnNodes;}

與鄰接矩陣的情況類(lèi)似，也可以對(duì)該程序“包裝”，以隱蔽visited和top。

第18頁(yè)，共44頁(yè)，2023年，2月20日，星期六

(三)非遞歸實(shí)現(xiàn)方法1．一般方法下面考慮深度優(yōu)先遍歷的非遞歸實(shí)現(xiàn)的一般方法（存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)）。圖的深度優(yōu)先遍歷的非遞歸實(shí)現(xiàn)，仍然與二叉樹(shù)的前序遍歷非遞歸實(shí)現(xiàn)相似。不同之處有：①二叉樹(shù)每個(gè)結(jié)點(diǎn)至多有兩個(gè)可達(dá)鄰接點(diǎn)（左右兒子），而圖的可達(dá)鄰接點(diǎn)數(shù)目不定，因此，當(dāng)結(jié)點(diǎn)重新出現(xiàn)在棧頂時(shí)，不能一定出棧，而是要根據(jù)它的各出點(diǎn)是否都已被訪問(wèn)過(guò)來(lái)決定（是則出棧）；②對(duì)二叉樹(shù)，沿可達(dá)鄰接點(diǎn)搜索時(shí)不會(huì)發(fā)生回繞，但對(duì)圖，若不加特別控制，就有可能回繞。

第19頁(yè)，共44頁(yè)，2023年，2月20日，星期六longDFS_NR(圖g，結(jié)點(diǎn)v0){//圖深度優(yōu)先遍歷非遞歸算法。從結(jié)點(diǎn)v0出發(fā)，深度優(yōu)先遍歷圖g，返回訪問(wèn)到的結(jié)點(diǎn)總數(shù)

intnNodes;//寄存訪問(wèn)到的結(jié)點(diǎn)數(shù)目訪問(wèn)v0;

為v0置已訪問(wèn)標(biāo)志;v0進(jìn)棧S；

nNodes=1;

求出v0的第1個(gè)可達(dá)鄰接點(diǎn)v;

深度優(yōu)先遍歷非遞歸算法的一般性描述。第20頁(yè)，共44頁(yè)，2023年，2月20日，星期六while(棧S不空){

v=棧S頂部元素；求v的下個(gè)未訪問(wèn)過(guò)的出點(diǎn)i；

訪問(wèn)i;

為i置已訪問(wèn)標(biāo)志;

i進(jìn)棧S；

nNodes++;

if(v已無(wú)未被訪問(wèn)過(guò)的出點(diǎn))出棧；

}returnnNodes;}

上面的偽碼描述與具體的數(shù)據(jù)結(jié)構(gòu)無(wú)關(guān)。下面的程序分別給出了針對(duì)鄰接矩陣與鄰接表的算法模型。

第21頁(yè)，共44頁(yè)，2023年，2月20日，星期六2．鄰接矩陣實(shí)現(xiàn)longDFS1_NR(intg[][CNST_NumNodes],longn,longv0,long*resu){//深度優(yōu)先遍歷圖(非遞歸）。圖g為鄰接矩陣，結(jié)點(diǎn)編號(hào)為0~n.返回實(shí)際遍歷到的結(jié)點(diǎn)數(shù)目

//resu為一維數(shù)組，用于存放所遍歷到的結(jié)點(diǎn)的編號(hào)，調(diào)用本函數(shù)前，應(yīng)為其分配空間

longnNodes,i,v;longtop;char*visited;long*s;visited=newchar[n];for(i=0;i<n;i++)visited[i]=0;

s=newlong[n+1];top=0;

nNodes=0;resu[nNodes++]=v0;//將訪問(wèn)到的結(jié)點(diǎn)依次存于resu[]visited[v0]=1;//為v0置已訪問(wèn)標(biāo)志第22頁(yè)，共44頁(yè)，2023年，2月20日，星期六

top++;s[top]=v0;while(top!=0){v=s[top];for(i=0;i<n;i++)//尋找v的下個(gè)未訪問(wèn)的鄰接點(diǎn)

if(g[v][i]!=0)//若<v,i>是邊

if(!visited[i])//若結(jié)點(diǎn)i未被訪問(wèn)過(guò)

{resu[nNodes++]=i;//將訪問(wèn)到的結(jié)點(diǎn)依次存于resu[]visited[i]=1;//為i置已訪問(wèn)標(biāo)志

top++;s[top]=i;//i進(jìn)棧

break;}if(i==n)top--;//若v已無(wú)未訪問(wèn)到的出點(diǎn)，則將其退棧

}//whilereturnnNodes;}第23頁(yè)，共44頁(yè)，2023年，2月20日，星期六下面給出初始結(jié)點(diǎn)為1時(shí)，得進(jìn)出棧的過(guò)程：15224111進(jìn)棧，1出棧；2進(jìn)棧，5進(jìn)棧，5出棧，2出棧，1進(jìn)棧，4進(jìn)棧，4出棧，1出棧。遍歷結(jié)果為1，5，2，4第24頁(yè)，共44頁(yè)，2023年，2月20日，星期六20.3深度優(yōu)先遍歷的性質(zhì)

深度優(yōu)先遍歷有許多重要而有趣的性質(zhì)，利用它們可以獲得有關(guān)圖的更多的信息。我們這里作一簡(jiǎn)單介紹。(一)深度優(yōu)先生成樹(shù)與單源路徑在深度優(yōu)先遍歷中，如果將每次“前進(jìn)”（縱深）路過(guò)的（將被訪問(wèn)的）結(jié)點(diǎn)和邊都記錄下來(lái)，就得到一個(gè)子圖，該子圖為以出發(fā)點(diǎn)為根的樹(shù)，稱為深度優(yōu)先生成樹(shù)。第25頁(yè)，共44頁(yè)，2023年，2月20日，星期六

如果從圖的多個(gè)結(jié)點(diǎn)出發(fā)才能遍歷到所有結(jié)點(diǎn)，則圖的深度優(yōu)先遍歷樹(shù)有多棵，從而構(gòu)成森林，稱為深度優(yōu)先生成森林。顯然，由圖得到深度優(yōu)先生成樹(shù)，相當(dāng)于對(duì)圖“層次”化，使圖中每個(gè)結(jié)點(diǎn)都有一個(gè)層次號(hào)。此外，從v0出發(fā)深度優(yōu)先遍歷樹(shù)，同時(shí)也產(chǎn)生v0到各結(jié)點(diǎn)的路徑。例如，圖

20?2(a)的出發(fā)點(diǎn)為1的深度優(yōu)先生成樹(shù)如圖

20?2(b).(a)有向圖(b)深度優(yōu)先生成樹(shù)圖20-2?深度優(yōu)先遍歷性質(zhì)說(shuō)明1254361254361/122/53/47/86/119/10第26頁(yè)，共44頁(yè)，2023年，2月20日，星期六(二)時(shí)間戳

在遍歷中，對(duì)每個(gè)結(jié)點(diǎn)v，定義從第一次“發(fā)現(xiàn)”（即第一次遇到，開(kāi)始遍歷）它的時(shí)刻為它的發(fā)現(xiàn)時(shí)間，記為S(v)，定義遍歷完v的時(shí)刻為v的完成時(shí)間，記為E(v)。這兩種時(shí)間都稱v的時(shí)間戳。一般情況下，用遍歷中“路過(guò)”（包括回退）的結(jié)點(diǎn)數(shù)表示時(shí)間。圖

20?2(b)中，結(jié)點(diǎn)旁邊的數(shù)字“a/b”表示對(duì)應(yīng)結(jié)點(diǎn)的開(kāi)始時(shí)間和完成時(shí)間分別為a和b（針對(duì)(a)的從1出發(fā)的深度優(yōu)先遍歷）。時(shí)間戳的差E(v)-S(v)可用在推算深度優(yōu)先遍歷的進(jìn)行情況，做為遍歷的啟發(fā)信息，指導(dǎo)遍歷算法盡快發(fā)現(xiàn)目標(biāo)。第27頁(yè)，共44頁(yè)，2023年，2月20日，星期六(三)遍歷括號(hào)某結(jié)點(diǎn)v的深度優(yōu)先遍歷括號(hào)定義為：

(vX1X2…Xmv)

這里，Xi為v的出點(diǎn)中，可從v出發(fā)直接訪問(wèn)到的各結(jié)點(diǎn)的遍歷括號(hào)。i=1,…,m，m≥0。例如，圖20?2(b)的結(jié)點(diǎn)1的遍歷括號(hào)為：按時(shí)間戳有

(1(2(44)2)(5(33)(66)5)1)

遍歷括號(hào)實(shí)質(zhì)上是廣義表，它完全描述了深度優(yōu)先遍歷的過(guò)程及深度優(yōu)先遍歷生成樹(shù)的結(jié)構(gòu)，可做為深度優(yōu)先遍歷生成樹(shù)的串行化表達(dá)式。第28頁(yè)，共44頁(yè)，2023年，2月20日，星期六20.4廣度優(yōu)先遍歷

(一)圖的廣度優(yōu)先分層

圖的廣度優(yōu)先分層與圖的廣度優(yōu)先遍歷密切相關(guān)。另外，在許多其他問(wèn)題中，也涉及到圖的廣度優(yōu)先分層。圖的廣度優(yōu)先分層就是要識(shí)別出圖中每個(gè)結(jié)點(diǎn)屬于的層次，即給每個(gè)結(jié)點(diǎn)編一個(gè)層次號(hào)。但是，圖本身是非層次結(jié)構(gòu)，所以，一般也無(wú)層次而言。然而，我們?nèi)糁粡哪承╆P(guān)系/角度考慮問(wèn)題，則就可對(duì)圖分層了。第29頁(yè)，共44頁(yè)，2023年，2月20日，星期六

分層時(shí)，應(yīng)先確定一個(gè)或幾個(gè)參考點(diǎn)，將它們的層號(hào)指定為起始層（第1層）。下面給出以結(jié)點(diǎn)v0為參考點(diǎn)的圖的廣度優(yōu)先分層的定義（非過(guò)程化），這里用Level(v)表示結(jié)點(diǎn)v的廣度優(yōu)先分層的層號(hào)：

n

令Level(v0)=1

n

對(duì)任意的v≠v0，若存在v0到v的通路，則令

Level(v)=1+MINu{Level(u)|<u,v>是圖的邊}

否則令Level(v)=∞

可能在不同的路徑中會(huì)有多個(gè)邊到達(dá)，取其最短者，即層號(hào)低的那個(gè)。第30頁(yè)，共44頁(yè)，2023年，2月20日，星期六例20?3對(duì)圖20?1，廣度優(yōu)先分層情況為：右圖：從1出發(fā)分層：層號(hào)為1的結(jié)點(diǎn)：1

層號(hào)為2的結(jié)點(diǎn)：2，5

層號(hào)為3的結(jié)點(diǎn)：4

層號(hào)為∞的結(jié)點(diǎn)：3

右圖：從2出發(fā)分層：層號(hào)為1的結(jié)點(diǎn)：2

層號(hào)為2的結(jié)點(diǎn)：1，4

層號(hào)為3的結(jié)點(diǎn)：5

層號(hào)為∞的結(jié)點(diǎn)：3

右圖：從a出發(fā)分層：層號(hào)為1的結(jié)點(diǎn)：a

層號(hào)為2的結(jié)點(diǎn)：b，d

層號(hào)為3的結(jié)點(diǎn)：c

12543abcd第31頁(yè)，共44頁(yè)，2023年，2月20日，星期六(二)圖的廣度優(yōu)先遍歷方法

從結(jié)點(diǎn)v0出發(fā)，廣度優(yōu)先遍歷（Breadth/WidthFirstSearch）圖的方法是，按從v0出發(fā)，對(duì)圖的廣度優(yōu)先分層的層次號(hào)的大小次序訪問(wèn)結(jié)點(diǎn)，即先訪問(wèn)第一層上結(jié)點(diǎn)，然后訪問(wèn)第二層上結(jié)點(diǎn)，…等等，同層上結(jié)點(diǎn)可按鄰接點(diǎn)次序或任意。例如，圖

20?1中的兩個(gè)圖的一些廣度優(yōu)先遍歷次序如下。左圖：從1出發(fā)廣度優(yōu)先遍歷結(jié)果：1，2，5，4

左圖：從2出發(fā)廣度優(yōu)先遍歷：2，1，4，5

右圖：從a出發(fā)廣度優(yōu)先遍歷：a，b，d，c

從另一角度看，從v出發(fā)廣度優(yōu)先遍歷，是先訪問(wèn)v，然后，對(duì)任意結(jié)點(diǎn)u，在訪問(wèn)了u之后，對(duì)u的各可達(dá)點(diǎn)的訪問(wèn)，按距u的距離（邊數(shù)）大小次序進(jìn)行。顯然，若圖的結(jié)點(diǎn)是無(wú)序的（即鄰接點(diǎn)無(wú)次序關(guān)系），則廣度優(yōu)先遍歷次序也不是唯一的，但層次關(guān)系不顛倒。

第32頁(yè)，共44頁(yè)，2023年，2月20日，星期六(三)算法實(shí)現(xiàn)

1.一般方法對(duì)于深度優(yōu)先遍歷，用遞歸方法描述是件自然的事，但廣度優(yōu)先遍歷不然，使用遞歸描述反而會(huì)使問(wèn)題復(fù)雜化，所以我們這里只講非遞歸描述法

廣度優(yōu)先遍歷是一種分層處理，對(duì)這種分層處理，使用隊(duì)列是自然的。我們?cè)O(shè)立一個(gè)隊(duì)列，任何時(shí)刻，均保證它滿足下列條件：

·隊(duì)中元素是已訪問(wèn)過(guò)的結(jié)點(diǎn)的可達(dá)鄰接點(diǎn)；

·隊(duì)中元素是尚未被訪問(wèn)過(guò)的；

·隊(duì)中元素按它們所處的層次的先后排列。這樣，我們就可不斷地每次從隊(duì)中取出一個(gè)元素并訪問(wèn)之，然后再將該元素的尚未被訪問(wèn)過(guò)的鄰接點(diǎn)進(jìn)隊(duì)，直至隊(duì)空。

第33頁(yè)，共44頁(yè)，2023年，2月20日，星期六

圖的廣度優(yōu)先算法偽碼描述如下：

longBFS(圖g,結(jié)點(diǎn)v0）

{//在圖g中從v0出發(fā)按廣度優(yōu)先遍歷方式遍歷g，返回遍歷到的結(jié)點(diǎn)數(shù)目

longnNodes=0;

初始化隊(duì)Q;

if（v0存在）

{v0入Q;

置v0為已訪問(wèn)標(biāo)志;

}

while(Q不空){

隊(duì)Q頭元素出隊(duì)并送v;

訪問(wèn)v;

nNodes++;//對(duì)已訪問(wèn)元素計(jì)數(shù)第34頁(yè)，共44頁(yè)，2023年，2月20日，星期六

求出v的第一個(gè)可達(dá)鄰接點(diǎn)w;

while(w存在)

{if(w尚未被訪問(wèn)過(guò))

{w入Q;置w為已訪問(wèn)標(biāo)志;

}

求v的下個(gè)可達(dá)鄰接點(diǎn)w;

}returnnNodes;}A

請(qǐng)思考，(1)如果上面的程序中不使用隊(duì)列，而所用棧，那么是否正確？為什么？(2)為什么結(jié)點(diǎn)一入隊(duì)就置已訪問(wèn)標(biāo)志？上面的算法描述是一般性的，并未涉及到具體的存貯結(jié)構(gòu)。第35頁(yè)，共44頁(yè)，2023年，2月20日，星期六2.鄰接矩陣實(shí)現(xiàn)設(shè)圖用鄰接矩陣表示，則它的廣度優(yōu)先遍歷算法如下。longBFS1_NR(intg[][CNST_NumNodes],longn,longv0,long*nos){//廣度優(yōu)先遍歷（鄰接矩陣）：從v0出發(fā)遍歷用鄰接矩陣表示的圖g（共n個(gè)結(jié)點(diǎn)）

//將訪問(wèn)到的結(jié)點(diǎn)的編號(hào)存入nos(其必須在外面分配n個(gè)long型空間），返回遍歷到的結(jié)點(diǎn)數(shù)目

longnNodes=0;longv,w,i;char*visited;TQueueSqu<long>Q(n+1);

visited=newchar[n];for(i=0;i<n;i++)visited[i]=0;//初始化訪問(wèn)標(biāo)志數(shù)組

if(v0>=0&&v0<n)第36頁(yè)，共44頁(yè)，2023年，2月20日，星期六

{Q.QPush(v0);visited[v0]=1;}while(!Q.IsEmpty()){v=Q.QPop();nos[nNodes]=v;//訪問(wèn)結(jié)點(diǎn)vnNodes++;for(w=0;w<n;w++)//找v的各未訪問(wèn)的出點(diǎn)

if(g[v][w]!=0)if(!visited[w]){Q.QPush(w);//v的各未訪問(wèn)的出點(diǎn)進(jìn)棧

visited[w]=1;}}//whiledelete[]visited;returnnNodes;}

第37頁(yè)，共44頁(yè)，2023年，2月20日，星期六12543

12345

101001210010300001410000500000所示圖的鄰接矩陣g1121304151

圖20?1有向圖訪問(wèn)標(biāo)識(shí)數(shù)組visited1254輸出數(shù)組nos

145425第38頁(yè)，共44頁(yè)，2023年，2月20日，星期六3．鄰接表實(shí)現(xiàn)針對(duì)鄰接表的算法為：

template<classTElem,classTEdgeElem>longBFS2_NR(TGraphNodeAL<TElem,TEdgeElem>*nodes,longn,longv0,long*nos){//廣度優(yōu)先遍歷（鄰接表）：從v0出發(fā)遍歷用鄰接表表示的圖g（共n個(gè)結(jié)點(diǎn)）

//將訪問(wèn)到的結(jié)點(diǎn)的編號(hào)存入nos(其必須在外面分配n個(gè)long型空間），返回遍歷到的結(jié)點(diǎn)數(shù)目

longnNodes=0;TGraphEdge*p;char*visited;TQueuesSqu<long>Q(n+1);

visited=newchar[n];for(i=0;i<n;i++)visited[i]=0;//初始化訪問(wèn)標(biāo)志數(shù)組

if