摘要: 簡(jiǎn)單說(shuō)一下回溯法，回溯跟深度優(yōu)先遍歷是分不開的，我們傾向于把回溯看做深度優(yōu)先遍歷的延伸。我們知道，圖的深度優(yōu)先遍歷每個(gè)節(jié)點(diǎn)只會(huì)被訪問(wèn)一次，因?yàn)槲覀円坏┳哌^(guò)一個(gè)點(diǎn)，我們就會(huì)做相應(yīng)的標(biāo)記，避免重復(fù)經(jīng)過(guò)同一個(gè)點(diǎn)。而回溯的做法是，當(dāng)走過(guò)某一個(gè)點(diǎn)時(shí)，標(biāo)記走過(guò)，并把該點(diǎn)壓棧；當(dāng)該節(jié)點(diǎn)出棧時(shí)，我們?cè)侔阉鼧?biāo)記為沒(méi)有走過(guò)，這樣就能保證另外一條路也能經(jīng)過(guò)該點(diǎn)了  閱讀全文      摘要: 圖的常見(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ò)  閱讀全文