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

圖的遍歷深度優(yōu)先遍歷和廣度優(yōu)先遍歷第一頁，共四十四頁，編輯于2023年，星期二20、圖的遍歷深度優(yōu)先遍歷和廣度優(yōu)先遍歷

掌握圖的深度優(yōu)先和廣度優(yōu)先遍歷的性質(zhì)和方法，以及基于鄰接矩陣和鄰接表存儲結(jié)構(gòu)的遞歸和非遞歸的算法實(shí)現(xiàn)第二頁，共四十四頁，編輯于2023年，星期二目錄20.1概述20.2深度優(yōu)先遍歷

20.3深度優(yōu)先遍歷的性質(zhì)20.4廣度優(yōu)先遍歷20.5廣度優(yōu)先遍歷的性質(zhì)第三頁，共四十四頁，編輯于2023年，星期二20、圖的遍歷

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

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

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

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

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

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

下面只考慮從一點(diǎn)出發(fā)遍歷，因此有可能會出現(xiàn)遍歷不到的點(diǎn)。即那些初始點(diǎn)無路徑可達(dá)的點(diǎn)，是遍歷不到的。第七頁，共四十四頁，編輯于2023年，星期二20.2深度優(yōu)先遍歷

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

·訪問v0；

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

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

第八頁，共四十四頁，編輯于2023年，星期二

例如，對圖

20?1給出的有向圖與無向圖，一些遍歷結(jié)果（結(jié)點(diǎ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一個有向圖（左）和無向圖第九頁，共四十四頁，編輯于2023年，星期二1.一般算法

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

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

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

訪問v0;

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

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

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

第十一頁，共四十四頁，編輯于2023年，星期二12543

12345

101001210010300001410000500000所示圖的鄰接矩陣g112130415

1

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

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

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

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

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

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

longnNodes,i;

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

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

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

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

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

}returnnNodes;}

第十四頁，共四十四頁，編輯于2023年，星期二

A

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

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

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;}第十五頁，共四十四頁，編輯于2023年，星期二1254312452b5^1d4^5^1^a1c2e3f4^5對應(yīng)的鄰接表圖20?2有向圖1121304151訪問標(biāo)識數(shù)組visited輸出數(shù)組resu地址起終權(quán)信息鏈a12bb15∧c21dd24∧e35∧f41∧

鄰接表邊PNodes[]

終點(diǎn)2作為下次的始點(diǎn)，由于1點(diǎn)已訪問過，跳過，找到4，記標(biāo)識，送輸出，4有作為新的始點(diǎn)重復(fù)上述過程第十六頁，共四十四頁，編輯于2023年，星期二

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)個數(shù)（編號為0~n）。

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

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

longnNodes,i;TGraphEdgeAL<TEdgeElem>*p;

nNodes=1;

第十七頁，共四十四頁，編輯于2023年，星期二

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

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

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

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

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

}returnnNodes;}

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

第十八頁，共四十四頁，編輯于2023年，星期二

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

第十九頁，共四十四頁，編輯于2023年，星期二longDFS_NR(圖g，結(jié)點(diǎn)v0){//圖深度優(yōu)先遍歷非遞歸算法。從結(jié)點(diǎn)v0出發(fā)，深度優(yōu)先遍歷圖g，返回訪問到的結(jié)點(diǎn)總數(shù)

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

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

nNodes=1;

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

深度優(yōu)先遍歷非遞歸算法的一般性描述。第二十頁，共四十四頁，編輯于2023年，星期二while(棧S不空){

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

訪問i;

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

i進(jìn)棧S；

nNodes++;

if(v已無未被訪問過的出點(diǎn))出棧；

}returnnNodes;}

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

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

//resu為一維數(shù)組，用于存放所遍歷到的結(jié)點(diǎn)的編號，調(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;//將訪問到的結(jié)點(diǎn)依次存于resu[]visited[v0]=1;//為v0置已訪問標(biāo)志第二十二頁，共四十四頁，編輯于2023年，星期二

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

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

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

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

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

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

}//whilereturnnNodes;}第二十三頁，共四十四頁，編輯于2023年，星期二下面給出初始結(jié)點(diǎn)為1時，得進(jìn)出棧的過程：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第二十四頁，共四十四頁，編輯于2023年，星期二20.3深度優(yōu)先遍歷的性質(zhì)

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

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

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

20?2(b).(a)有向圖(b)深度優(yōu)先生成樹圖20-2?深度優(yōu)先遍歷性質(zhì)說明1254361254361/122/53/47/86/119/10第二十六頁，共四十四頁，編輯于2023年，星期二(二)時間戳

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

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

(vX1X2…Xmv)

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

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

遍歷括號實(shí)質(zhì)上是廣義表，它完全描述了深度優(yōu)先遍歷的過程及深度優(yōu)先遍歷生成樹的結(jié)構(gòu)，可做為深度優(yōu)先遍歷生成樹的串行化表達(dá)式。第二十八頁，共四十四頁，編輯于2023年，星期二20.4廣度優(yōu)先遍歷

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

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

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

n

令Level(v0)=1

n

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

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

否則令Level(v)=∞

可能在不同的路徑中會有多個邊到達(dá)，取其最短者，即層號低的那個。第三十頁，共四十四頁，編輯于2023年，星期二例20?3對圖20?1，廣度優(yōu)先分層情況為：右圖：從1出發(fā)分層：層號為1的結(jié)點(diǎn)：1

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

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

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

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

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

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

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

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

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

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

12543abcd第三十一頁，共四十四頁，編輯于2023年，星期二(二)圖的廣度優(yōu)先遍歷方法

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

20?1中的兩個圖的一些廣度優(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)先遍歷，是先訪問v，然后，對任意結(jié)點(diǎn)u，在訪問了u之后，對u的各可達(dá)點(diǎn)的訪問，按距u的距離（邊數(shù)）大小次序進(jìn)行。顯然，若圖的結(jié)點(diǎn)是無序的（即鄰接點(diǎn)無次序關(guān)系），則廣度優(yōu)先遍歷次序也不是唯一的，但層次關(guān)系不顛倒。

第三十二頁，共四十四頁，編輯于2023年，星期二(三)算法實(shí)現(xiàn)

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

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

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

·隊(duì)中元素是尚未被訪問過的；

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

第三十三頁，共四十四頁，編輯于2023年，星期二

圖的廣度優(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為已訪問標(biāo)志;

}

while(Q不空){

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

訪問v;

nNodes++;//對已訪問元素計(jì)數(shù)第三十四頁，共四十四頁，編輯于2023年，星期二

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

while(w存在)

{if(w尚未被訪問過)

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

}

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

}returnnNodes;}A

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

//將訪問到的結(jié)點(diǎn)的編號存入nos(其必須在外面分配n個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;//初始化訪問標(biāo)志數(shù)組

if(v0>=0&&v0<n)第三十六頁，共四十四頁，編輯于2023年，星期二

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

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

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

第三十七頁，共四十四頁，編輯于2023年，星期二12543

12345

101001210010300001410000500000所示圖的鄰接矩陣g1121304151

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

145425第三十八頁，共四十四頁，編輯于2023年，星期二3．鄰接表實(shí)現(xiàn)針對鄰接表的算法為：

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

//將訪問到的結(jié)點(diǎn)的編號存入nos(其必須在外面分配n個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;//初始化訪問標(biāo)志數(shù)組

if