本章會(huì)先對(duì)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索進(jìn)行介紹，然后再給出C/C++/Java的實(shí)現(xiàn),。

目錄
1. 深度優(yōu)先搜索的圖文介紹
1.1 深度優(yōu)先搜索介紹
1.2 深度優(yōu)先搜索圖解
2. 廣度優(yōu)先搜索的圖文介紹
2.1 廣度優(yōu)先搜索介紹
2.2 廣度優(yōu)先搜索圖解
3. 搜索算法的源碼

轉(zhuǎn)載請(qǐng)注明出處：http://www.cnblogs.com/skywang12345/

更多內(nèi)容：數(shù)據(jù)結(jié)構(gòu)與算法系列 目錄

深度優(yōu)先搜索的圖文介紹

1. 深度優(yōu)先搜索介紹

圖的深度優(yōu)先搜索(Depth First Search),，和樹的先序遍歷比較類似。

它的思想：假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)均未被訪問,，則從某個(gè)頂點(diǎn)v出發(fā),，首先訪問該頂點(diǎn)，然后依次從它的各個(gè)未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖,，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問到,。 若此時(shí)尚有其他頂點(diǎn)未被訪問到，則另選一個(gè)未被訪問的頂點(diǎn)作起始點(diǎn),，重復(fù)上述過程,，直至圖中所有頂點(diǎn)都被訪問到為止。

顯然,，深度優(yōu)先搜索是一個(gè)遞歸的過程。

2. 深度優(yōu)先搜索圖解

2.1 無向圖的深度優(yōu)先搜索

下面以"無向圖"為例,，來對(duì)深度優(yōu)先搜索進(jìn)行演示,。

對(duì)上面的圖G1進(jìn)行深度優(yōu)先遍歷，從頂點(diǎn)A開始,。

第1步：訪問A,。
第2步：訪問(A的鄰接點(diǎn))C。
    在第1步訪問A之后，接下來應(yīng)該訪問的是A的鄰接點(diǎn),，即"C,D,F"中的一個(gè),。但在本文的實(shí)現(xiàn)中，頂點(diǎn)ABCDEFG是按照順序存儲(chǔ),，C在"D和F"的前面,，因此，先訪問C,。
第3步：訪問(C的鄰接點(diǎn))B,。
    在第2步訪問C之后，接下來應(yīng)該訪問C的鄰接點(diǎn),，即"B和D"中一個(gè)(A已經(jīng)被訪問過,，就不算在內(nèi))。而由于B在D之前,，先訪問B,。
第4步：訪問(C的鄰接點(diǎn))D。
    在第3步訪問了C的鄰接點(diǎn)B之后,，B沒有未被訪問的鄰接點(diǎn),；因此，返回到訪問C的另一個(gè)鄰接點(diǎn)D,。
第5步：訪問(A的鄰接點(diǎn))F,。
    前面已經(jīng)訪問了A，并且訪問完了"A的鄰接點(diǎn)B的所有鄰接點(diǎn)(包括遞歸的鄰接點(diǎn)在內(nèi))",；因此,，此時(shí)返回到訪問A的另一個(gè)鄰接點(diǎn)F。
第6步：訪問(F的鄰接點(diǎn))G,。
第7步：訪問(G的鄰接點(diǎn))E,。

因此訪問順序是：A -> C -> B -> D -> F -> G -> E

2.2 有向圖的深度優(yōu)先搜索

下面以"有向圖"為例，來對(duì)深度優(yōu)先搜索進(jìn)行演示,。

對(duì)上面的圖G2進(jìn)行深度優(yōu)先遍歷,，從頂點(diǎn)A開始。

第1步：訪問A,。
第2步：訪問B,。
    在訪問了A之后，接下來應(yīng)該訪問的是A的出邊的另一個(gè)頂點(diǎn),，即頂點(diǎn)B,。
第3步：訪問C。
    在訪問了B之后,，接下來應(yīng)該訪問的是B的出邊的另一個(gè)頂點(diǎn),，即頂點(diǎn)C,E,F,。在本文實(shí)現(xiàn)的圖中，頂點(diǎn)ABCDEFG按照順序存儲(chǔ),，因此先訪問C,。
第4步：訪問E。
    接下來訪問C的出邊的另一個(gè)頂點(diǎn),，即頂點(diǎn)E,。
第5步：訪問D。
    接下來訪問E的出邊的另一個(gè)頂點(diǎn),，即頂點(diǎn)B,D,。頂點(diǎn)B已經(jīng)被訪問過，因此訪問頂點(diǎn)D,。
第6步：訪問F,。
    接下應(yīng)該回溯"訪問A的出邊的另一個(gè)頂點(diǎn)F"。
第7步：訪問G,。

因此訪問順序是：A -> B -> C -> E -> D -> F -> G

廣度優(yōu)先搜索的圖文介紹

1. 廣度優(yōu)先搜索介紹

廣度優(yōu)先搜索算法(Breadth First Search),，又稱為"寬度優(yōu)先搜索"或"橫向優(yōu)先搜索"，簡(jiǎn)稱BFS,。

它的思想是：從圖中某頂點(diǎn)v出發(fā),，在訪問了v之后依次訪問v的各個(gè)未曾訪問過的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問它們的鄰接點(diǎn),，并使得“先被訪問的頂點(diǎn)的鄰接點(diǎn)先于后被訪問的頂點(diǎn)的鄰接點(diǎn)被訪問,，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。如果此時(shí)圖中尚有頂點(diǎn)未被訪問,，則需要另選一個(gè)未曾被訪問過的頂點(diǎn)作為新的起始點(diǎn),，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止,。

換句話說,，廣度優(yōu)先搜索遍歷圖的過程是以v為起點(diǎn)，由近至遠(yuǎn),，依次訪問和v有路徑相通且路徑長(zhǎng)度為1,2...的頂點(diǎn),。

2. 廣度優(yōu)先搜索圖解

2.1 無向圖的廣度優(yōu)先搜索

下面以"無向圖"為例，來對(duì)廣度優(yōu)先搜索進(jìn)行演示,。還是以上面的圖G1為例進(jìn)行說明,。

第1步：訪問A。
第2步：依次訪問C,D,F,。
    在訪問了A之后,，接下來訪問A的鄰接點(diǎn)。前面已經(jīng)說過,，在本文實(shí)現(xiàn)中,，頂點(diǎn)ABCDEFG按照順序存儲(chǔ)的，C在"D和F"的前面,，因此,，先訪問C。再訪問完C之后,，再依次訪問D,F,。
第3步：依次訪問B,G。
    在第2步訪問完C,D,F之后,，再依次訪問它們的鄰接點(diǎn),。首先訪問C的鄰接點(diǎn)B，再訪問F的鄰接點(diǎn)G,。
第4步：訪問E,。
    在第3步訪問完B,G之后，再依次訪問它們的鄰接點(diǎn),。只有G有鄰接點(diǎn)E,，因此訪問G的鄰接點(diǎn)E。

因此訪問順序是：A -> C -> D -> F -> B -> G -> E

2.2 有向圖的廣度優(yōu)先搜索

下面以"有向圖"為例,，來對(duì)廣度優(yōu)先搜索進(jìn)行演示,。還是以上面的圖G2為例進(jìn)行說明。

第1步：訪問A,。
第2步：訪問B,。
第3步：依次訪問C,E,F。
    在訪問了B之后,，接下來訪問B的出邊的另一個(gè)頂點(diǎn),，即C,E,F。前面已經(jīng)說過,，在本文實(shí)現(xiàn)中,，頂點(diǎn)ABCDEFG按照順序存儲(chǔ)的，因此會(huì)先訪問C,，再依次訪問E,F,。
第4步：依次訪問D,G。
    在訪問完C,E,F之后,，再依次訪問它們的出邊的另一個(gè)頂點(diǎn),。還是按照C,E,F的順序訪問，C的已經(jīng)全部訪問過了,，那么就只剩下E,F,；先訪問E的鄰接點(diǎn)D，再訪問F的鄰接點(diǎn)G,。

因此訪問順序是：A -> B -> C -> E -> F -> D -> G

搜索算法的源碼

這里分別給出"鄰接矩陣無向圖",、"鄰接表無向圖",、"鄰接矩陣有向圖"、"鄰接表有向圖"的C/C++/Java搜索算法源碼,。這里就不再對(duì)源碼進(jìn)行說明,，please RTFSC；參考源碼中的注釋進(jìn)行了解,。

1. C語言源碼
1.1 鄰接矩陣實(shí)現(xiàn)的無向圖(matrixudg.c)
1.2 鄰接表實(shí)現(xiàn)的無向圖(listudg.c)
1.3 鄰接矩陣實(shí)現(xiàn)的有向圖(matrixdg.c)
1.4 鄰接表實(shí)現(xiàn)的有向圖(listdg.c)

2. C++源碼
2.1 鄰接矩陣實(shí)現(xiàn)的無向圖(MatrixUDG.cpp)
2.2 鄰接表實(shí)現(xiàn)的無向圖(ListUDG.cpp)
2.3 鄰接矩陣實(shí)現(xiàn)的有向圖(MatrixDG.cpp)
2.4 鄰接表實(shí)現(xiàn)的有向圖(ListDG.cpp)

3. Java源碼
3.1 鄰接矩陣實(shí)現(xiàn)的無向圖(MatrixUDG.java)
3.2 鄰接表實(shí)現(xiàn)的無向圖(ListUDG.java)
3.3 鄰接矩陣實(shí)現(xiàn)的有向圖(MatrixDG.java)
3.4 鄰接表實(shí)現(xiàn)的有向圖(ListDG.java)