圖的常見遍歷方式有兩種：深度優(yōu)先遍歷和廣度優(yōu)先遍歷，他們的作用是將圖中的每個(gè)點(diǎn)都訪問一遍，只不過是順序不同。
如果把圖中的每條邊長都相等（比如都是1）的話，深度優(yōu)先遍歷的過程是：
1.任意選定一個(gè)點(diǎn)p0作為遍歷的起點(diǎn)
2.從未訪問節(jié)點(diǎn)中任選一個(gè)距離p0最近的點(diǎn)進(jìn)行訪問，并標(biāo)記該點(diǎn)被訪問過
3.重復(fù)第2步，直到該連通分支中的所有節(jié)點(diǎn)都被訪問過
說的形象一點(diǎn)，深度優(yōu)先遍歷就是按照層次的順序訪問節(jié)點(diǎn)，每一層中的節(jié)點(diǎn)與p0有相同的距離。先訪問第一層，再訪問第二層，……
深度優(yōu)先遍歷過程就是盡可能深的去訪問節(jié)點(diǎn)，具體過程為：
1.任意選定一個(gè)點(diǎn)p0作為遍歷的起點(diǎn)
2.當(dāng)訪問到某一個(gè)節(jié)點(diǎn)p1時(shí)，如果p1下面有未被遍歷的子節(jié)點(diǎn)，我們就接著訪問p1的某一個(gè)未被遍歷子節(jié)點(diǎn)，并標(biāo)記該子節(jié)點(diǎn)被訪問過，
3.如果p1不存在未被訪問的子節(jié)點(diǎn)，我們就退回到p1的父節(jié)點(diǎn)，并執(zhí)行第2步
4.執(zhí)行第2、3步，直到所有節(jié)點(diǎn)被訪問過。
（遞歸過程真心不好描述啊~~~）
大家也看出來了，深度優(yōu)先遍歷的是一個(gè)遞歸的過程，因此很容易想到要用到棧這種數(shù)據(jù)結(jié)構(gòu)，具體實(shí)現(xiàn)的時(shí)候可以用遞歸，也可以用棧。看個(gè)人習(xí)慣了。
廣度優(yōu)先遍歷實(shí)現(xiàn)就要用到隊(duì)列了。
以下是poj2386不同實(shí)現(xiàn)方式的代碼
深度優(yōu)先遍歷，遞歸實(shí)現(xiàn)：