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

【資料圖】

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

主要思想：

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

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

適用范圍：

有關于圖的問題。

例題：

例1

例2

總結：

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

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

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

#注：例題答案請查看視頻。

關鍵詞：