深度優(yōu)先搜索——不撞南墻不回頭

配套視頻：深度優(yōu)先搜索——不撞南墻不回頭

主要思想：

????深度優(yōu)先搜索,又稱DFS，是一種常用的圖搜索算法，常用于解決圖的遍歷、路徑查找、連通性判斷等問(wèn)題。它以深度為優(yōu)先級(jí)，不斷深入地探索圖中的節(jié)點(diǎn)，直到達(dá)到最大深度或無(wú)法進(jìn)一步探索為止。它是一種遞歸算法，基本思想是：從圖中的某個(gè)節(jié)點(diǎn)出發(fā)，沿著一條路徑盡可能深入地搜索，直到達(dá)到最深處或無(wú)法繼續(xù)搜索為止，然后回溯到前一節(jié)點(diǎn)，再沿著另一條路徑進(jìn)行深入搜索。當(dāng)所有節(jié)點(diǎn)都被訪問(wèn)完畢時(shí)，算法結(jié)束。深度優(yōu)先搜索的關(guān)鍵就在于標(biāo)記已訪問(wèn)的節(jié)點(diǎn)以避免重復(fù)訪問(wèn)。常用的標(biāo)記方式是使用一個(gè)Bool數(shù)組，將每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的位置設(shè)為已訪問(wèn)。

????深度優(yōu)先查找正詮釋了什么叫“不撞南墻不回頭”。

適用范圍：

????有關(guān)于圖的問(wèn)題。

例題：

例1

例2

總結(jié)：

????總結(jié)一下，今天我們聊了聊【深度優(yōu)先搜索】，它是一種簡(jiǎn)單而強(qiáng)大的圖搜索算法。它通過(guò)遞歸實(shí)現(xiàn)，以深度為優(yōu)先級(jí)進(jìn)行節(jié)點(diǎn)遍歷，能夠解決許多圖相關(guān)的問(wèn)題。

????在具體實(shí)現(xiàn)該算法時(shí)，可以選擇使用遞歸。遞歸函數(shù)在進(jìn)入每一層時(shí)都會(huì)進(jìn)行訪問(wèn)標(biāo)記，回溯時(shí)再取消標(biāo)記。

好啦，關(guān)于深度優(yōu)先搜索就說(shuō)到這里。這里是康郭聊算法，拜拜！

#注：例題答案請(qǐng)查看視頻。