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