圖以及深度優(yōu)先和廣度優(yōu)先(修改版)

引言：

圖是一種非線性數(shù)據(jù)結(jié)構(gòu)。在圖結(jié)構(gòu)中，數(shù)據(jù)元素之間的關(guān)系是多對多的，即如果任選一個頂點(diǎn)作為初始頂點(diǎn)，則圖中任意一個頂點(diǎn)有多個前驅(qū)頂點(diǎn)和多個后記頂點(diǎn)。這次實(shí)驗(yàn)課提前給大家拓展一些圖方面的知識，并在此基礎(chǔ)之上引入圖的兩種搜索方法（廣度優(yōu)先和深度優(yōu)先）讓大家來學(xué)習(xí)。1圖的基本概念

圖是由頂點(diǎn)集合及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)。圖G的定義是：

G=（V，E）其中，V={x|x∈某個數(shù)據(jù)元素集合}E={(x，y)|x，y∈V}（x，y）表示從x到y(tǒng)的一條雙向通路，即（x，y）是無方向的；Path（x，y）表示從x到y(tǒng)的一條單向通路，即Path（x，y）是有方向的。2

圖的基本描述頂點(diǎn)和邊：圖中的結(jié)點(diǎn)稱作頂點(diǎn)，圖中的第i個頂點(diǎn)記做vi。兩個頂點(diǎn)vi和vj相關(guān)聯(lián)稱作頂點(diǎn)vi和vj之間有一條邊，圖中的第k條邊記做ek，ek=（vi,vj）或＜vi,vj＞。有向圖和無向圖：在有向圖中，頂點(diǎn)對＜x,y＞是有序的，頂點(diǎn)對＜x,y＞稱為從頂點(diǎn)x到頂點(diǎn)y的一條有向邊，有向圖中的邊也稱作?。辉跓o向圖中，頂點(diǎn)對（x,y）是無序的，頂點(diǎn)對（x,y）稱為與頂點(diǎn)x和頂點(diǎn)y相關(guān)聯(lián)的一條邊。完全圖：在有n個頂點(diǎn)的無向圖中，若有n(n-1)/2條邊，即任意兩個頂點(diǎn)之間有且只有一條邊，則稱此圖為無向完全圖；在有n個頂點(diǎn)的有向圖中，若有n(n-1)條邊，即任意兩個頂點(diǎn)之間有且只有方向相反的兩條邊，則稱此圖為有向完全圖。3有向圖和無向圖實(shí)例214532134有向圖無向圖4鄰接頂點(diǎn)：在無向圖G中，若（u,v）是E(G)中的一條邊，則稱u和v互為鄰接頂點(diǎn)，并稱邊（u,v）依附于頂點(diǎn)u和v；在有向圖G中，若＜u,v＞是E(G)中的一條邊，則稱頂點(diǎn)u鄰接到頂點(diǎn)v，頂點(diǎn)v鄰接自頂點(diǎn)u，并稱邊＜u,v＞和頂點(diǎn)u和頂點(diǎn)v相關(guān)聯(lián)。路徑：在圖G=(V,E)中，若從頂點(diǎn)vi出發(fā)有一組邊使可到達(dá)頂點(diǎn)vj，則稱頂點(diǎn)vi到頂點(diǎn)vj的頂點(diǎn)序列為從頂點(diǎn)vi到頂點(diǎn)vj的路徑。權(quán)：有些圖的邊附帶有數(shù)據(jù)信息，這些附帶的數(shù)據(jù)信息稱為權(quán)。帶權(quán)的圖也稱作網(wǎng)絡(luò)或網(wǎng)。路徑長度：對于不帶權(quán)的圖，一條路徑的路徑長度是指該路徑上的邊的條數(shù)；對于帶權(quán)的圖，一條路徑的路徑長度是指該路徑上各個邊權(quán)值的總和。5

要表示一個圖，有兩種標(biāo)準(zhǔn)的方法，即鄰接表和鄰接矩陣。這兩種表示法既可用于有向圖，也可用于無向圖。

在實(shí)踐中我們通常采用的是鄰接表表示法，因?yàn)檫@種方法表示稀疏圖（圖中的邊遠(yuǎn)遠(yuǎn)小于圖中的結(jié)點(diǎn)）比較緊湊。但是，當(dāng)遇到稠密圖時，或者必須很快判別兩個給定的定點(diǎn)是否存在連接邊時，通常采用鄰接矩陣表示法。圖的存儲結(jié)構(gòu)6圖的兩種表示方法：21543123455/4/4/3/2/鄰接表鄰接矩陣7廣度優(yōu)先搜索法：以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)，即對下一層節(jié)點(diǎn)搜索前，必須先搜索完本層所有節(jié)點(diǎn)深度優(yōu)先搜索法：首先擴(kuò)展最新產(chǎn)生的節(jié)點(diǎn)，每層只對一個節(jié)點(diǎn)進(jìn)行擴(kuò)展，除非搜索失敗或已達(dá)到預(yù)先約定的最大深度，才會退回去搜索原來忽略節(jié)點(diǎn)兩種經(jīng)典的搜索方法8廣度優(yōu)先搜索

廣度優(yōu)先搜索是最簡單的圖搜索算法之一，也是很多重要的圖算法的原型。

在給定圖和一個特定源定點(diǎn)S的情況下，廣度優(yōu)先將系統(tǒng)的搜索圖中的邊。該搜索算法之所以成為廣度優(yōu)先搜索，是因?yàn)樗冀K將已發(fā)現(xiàn)和未發(fā)現(xiàn)定點(diǎn)之間的邊界沿著其廣度方向向外拓展。即，算法首先會發(fā)現(xiàn)和S距離為K的定點(diǎn)，然后才會發(fā)現(xiàn)和S距離為K+1的其他頂點(diǎn)。

下面的廣度優(yōu)先搜索過程BFS假定輸入圖G=(V,E)采用鄰接表Adj表示，對于圖中的每個頂點(diǎn)還采用幾種另外的數(shù)據(jù)結(jié)構(gòu)，對于每個頂點(diǎn)u∈V,其標(biāo)注色彩存儲于color[u]中，u的父結(jié)點(diǎn)存于變量p[u]中。由該算法計算出來的源頂點(diǎn)s和u之間的距離存于變量d[u]中。該算法還使用了一個先進(jìn)先出隊(duì)列Q來管理所有的灰色頂點(diǎn)。圖的搜索9算法偽代碼：算法的一到四行是對除了原點(diǎn)S以外的所有點(diǎn)進(jìn)行初始化操作。

算法的五到九行是對源S進(jìn)行初始化，并使其入隊(duì)。

算法的十到十七行執(zhí)行取出隊(duì)列的第一個元素并求出它的后記頂點(diǎn)，然后對后記頂點(diǎn)的值進(jìn)行修改。

最后一行對剛出隊(duì)的元素進(jìn)行顏色修改，以此來標(biāo)記在其深度上廣度優(yōu)先算法完成。此處要改動！改為：color[v]=GRAY10深度優(yōu)先搜索

與廣度優(yōu)先搜索類似，在深度優(yōu)先算法中，也通過度定點(diǎn)進(jìn)行著色來表示定點(diǎn)的狀態(tài)。開始時，每個頂點(diǎn)均標(biāo)記為白色，搜索過程中被發(fā)現(xiàn)則設(shè)置成為灰色，結(jié)束時又被設(shè)置成黑色（即當(dāng)鄰接表被完全檢索之后）。這一技巧可以保證每一個頂點(diǎn)在搜索結(jié)束時，只存在于一棵深度優(yōu)先樹中，因此，這些樹是不相交的。

除了創(chuàng)建一個深度優(yōu)先森林以外，深度優(yōu)先搜索同時為每個頂點(diǎn)加蓋時間戳。每個頂點(diǎn)v有兩個時間戳：當(dāng)頂點(diǎn)v第一次被發(fā)現(xiàn)的時候（并設(shè)置成灰色），記錄下第一個時間戳d[v],當(dāng)結(jié)束檢查v的鄰接表（并設(shè)置為黑色）時，記錄下第二個時間戳f[v]。許多圖的算法中都用到了時間戳，它們對推算深度優(yōu)先搜索的進(jìn)行情況有很大幫助。11下面給出的DFS記錄了何時在變量d[u]中發(fā)現(xiàn)頂點(diǎn)u，以及何時在變量f[u]中完成對頂點(diǎn)u的檢索。這些時間戳為1到2|V|之間的整數(shù)，因?yàn)閷τ趞V|個頂點(diǎn)中的每一個，都對應(yīng)一個發(fā)生事件和一個完成事件。對每個頂點(diǎn)u有d[u]<f[u]。

頂點(diǎn)u在時刻d[u]之前為白色，在時刻d[u]和f[u]之間為灰色，以后就變成了黑色。12算法偽代碼：一到三行把所有頂點(diǎn)設(shè)置為白色，所有p域初始化為NULL。第四行復(fù)位全局計數(shù)器，五到七行檢索V中的頂點(diǎn)，發(fā)現(xiàn)白色頂點(diǎn)調(diào)用DFS-VISIT進(jìn)行訪問。每次通過第七行，u成為了深度優(yōu)