圖結(jié)構(gòu)遍歷的方法：深度優(yōu)先，廣度優(yōu)先

深度優(yōu)先遍歷是按照深度優(yōu)先搜索（Depth First Search,DFS）的方式對(duì)圖進(jìn)行遍歷。

深度優(yōu)先搜索是最常見得圖搜索方法之一。深度優(yōu)先搜索沿著一條路徑一直走下去，無法行進(jìn)時(shí)，回退到剛剛訪問的節(jié)點(diǎn)，似不撞南墻不回頭，不到黃河不死心。

????深度優(yōu)先遍歷秘籍：

????后被訪問的頂點(diǎn)，其鄰接點(diǎn)先被訪問。

????根據(jù)深度優(yōu)先遍歷秘籍，后來先服務(wù)，可以借助于棧實(shí)現(xiàn)。由于遞歸本身是使用棧實(shí)現(xiàn)的，因此使用遞歸方法更方便。

????算法步驟：

????1.初始化圖中所有頂點(diǎn)未被訪問。

????2.從圖中的某個(gè)頂點(diǎn)v出發(fā)，訪問v并標(biāo)記為被訪問。

????3.依次檢查v的所有鄰接點(diǎn)w,如果w未被訪問，則從w出發(fā)進(jìn)行深度優(yōu)先遍歷（遞歸調(diào)用，重復(fù)2-3步）。

廣度優(yōu)先遍歷是按照廣度優(yōu)先搜索（Breadth First Search ,BFS）的方式對(duì)圖進(jìn)行遍歷，又稱寬度優(yōu)先 。

廣度優(yōu)先搜索是最常見的圖搜索方法之一。廣度優(yōu)先搜索是從某一個(gè)頂點(diǎn)（源點(diǎn)）出發(fā)，一次性訪問所有未被訪問的鄰接點(diǎn)，再依次從這些訪問過鄰接點(diǎn)出發(fā)，...，似水中漣漪，似聲音傳播，一層層得傳播開來。

????廣度優(yōu)先遍歷秘籍 ：

????先被訪問的頂點(diǎn)，其鄰接點(diǎn)先被訪問。

????根據(jù)廣度優(yōu)先遍歷秘籍，先來先服務(wù)，可以借助于隊(duì)列來實(shí)現(xiàn)。每個(gè)節(jié)點(diǎn)訪問一次且只訪問一次，因此可以設(shè)置一個(gè)輔助數(shù)組：

????visited[i] = false,表示第i個(gè)頂點(diǎn)未訪問；

????visited[i] = true,表示第i個(gè)頂點(diǎn)已經(jīng)訪問。

????算法步驟：

????1.初始化圖中所有頂點(diǎn)未被訪問，初始化一個(gè)空隊(duì)列。

????2.從圖中的某個(gè)頂點(diǎn)v出發(fā)，訪問v并標(biāo)記已經(jīng)訪問，將v入隊(duì)；

????3.如果隊(duì)列非空，則繼續(xù)執(zhí)行，否則算法結(jié)束；

????4.隊(duì)頭元素v出隊(duì)，依次訪問v的所有未被訪問鄰接點(diǎn)，標(biāo)記已訪問并入隊(duì)。轉(zhuǎn)向步驟3；

????

????