定義
深度優先搜尋算法（Depth-First-Search），是搜尋算法的一種。是沿著樹的深度遍歷樹的節點，儘可能深的搜尋樹的分支。當節點v的所有邊都己被探尋過，搜尋將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重複以上過程，整個進程反覆進行直到所有節點都被訪問為止。屬於盲目搜尋。
深度優先搜尋是圖論中的經典算法，利用深度優先搜尋算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。
因發明“深度優先搜尋算法”，霍普克洛夫特與陶爾揚共同獲得計算機領域的最高獎：圖靈獎.
圖的遍歷
方法步驟
假設初始狀態是圖中所有頂點都未被訪問，則深度優先搜尋方法的步驟是：
1）選取圖中某一頂點Vi為出發點，訪問並標記該頂點；
2）以Vi為當前頂點，依次搜尋Vi的每個鄰接點Vj，若Vj未被訪問過，則訪問和標記鄰接點Vj，若Vj已被訪問過，則搜尋Vi的下一個鄰接點；
3）以Vj為當前頂點，重複步驟2），直到圖中和Vi有路徑相通的頂點都被訪問為止；
4）若圖中尚有頂點未被訪問過（非連通的情況下），則可任取圖中的一個未被訪問的頂點作為出發點，重複上述過程，直至圖中所有頂點都被訪問。
例1.迷宮問題
問題
首先，我們來想像一隻老鼠，在一座不見天日的迷宮內，老鼠在入口處進去，要從出口出來。那老鼠會怎么走？當然是這樣的：老鼠如果遇到直路，就一直往前走，如果遇到分叉路口，就任意選擇其中的一個繼續往下走，如果遇到死胡同，就退回到最近的一個分叉路口，選擇另一條道路再走下去，如果遇到了出口，老鼠的旅途就算結束了。深度優先搜尋法的基本原則就是這樣：按照某種條件往前試探搜尋，如果前進中遭到失敗（正如老鼠遇到死胡同），則退回頭另選通路繼續搜尋，直到找到條件的目標為止。
遞歸算法
實現這一算法，我們要用到編程的一大利器--遞歸。“遞歸”是一個很抽象的概念， 但是在日常生活中，我們還是能夠看到的。拿兩面鏡子來，把他們面對著面，你會看到什麼？你會看到鏡子中 有無數個鏡子？怎么回事？A鏡子中有B鏡子的象，B鏡子中有A鏡子的象，A鏡子的象就是A鏡子本身的真實寫照，也就是說A鏡子的象包括了A鏡子，還有B鏡子在A鏡子中的象………………好累啊，又煩又繞口，還不好理解。換成計算機語言就是A調用B，而B又調用A，這樣間接的，A就調用了A本身，這實現了一個重複的功能。
再舉一個例子：從前有座山，山裡有座廟，廟裡有個老和尚，老和尚在講故事，講什麼呢？講：從前有座山，山裡有座廟，廟裡有個老和尚，老和尚在講故事，講什麼呢？講：從前有座山，山裡有座廟，廟裡有個老和尚， 老和尚在講故事，講什麼呢？講：…………。好傢夥，這樣講到世界末日還講不完，老和尚講的故事實際上就是前面的故事情節，這樣不斷地調用程式本身，就形成了遞歸。 萬一這個故事中的某一個老和尚看這個故事不順眼，就把他要講的故事換成：“你有完沒完啊！”，這樣，整個故事也就嘎然而止了。我們編程就要注意這一點，在適當的時候，就必須要有一個這樣的和尚挺身而出，把整個故事給停下來，或者使他不再往深一層次搜尋，要不，遞歸就會因計算機存儲容量的限制而被迫溢出，切記，切記。
解法
我們把遞歸思想運用到上面的迷宮中，記老鼠現在所在的位置是(x,y),那它現在有前後左右4個方向可以走，分別是(x+1,y),(x-1,y),(x,y+1),(x,y-1),其中一個方向是它來時的路，我們先不考慮，我們就分別嘗試其他三個方向，如果某個方向是路而不是牆的話，老鼠就向那個方向邁出一步。在新的位置上，我們又可以重複前面的步驟。老鼠走到了死胡同又是怎么回事？就是除了來時的路，其他3個方向都是牆，這時這條路就走到了盡頭，無法再向深一層發展，我們就應該沿來時的路回去，嘗試另外的方向。
例2.八皇后問題
問題
八皇后問題：在標準西洋棋的棋盤上（8*8格）準備放置8隻皇后，我們知 道，西洋棋中皇后的威力是最大的，她既可以橫走豎走，還可以斜著走，遇到擋在她前進路線上的敵人，她 就可以吃掉對手。要求在棋盤上安放8隻皇后，使她們彼此互相都不能吃到對方，求皇后的放法。
解法
這是一道很經典的題目了，我們先要明確一下思路，如何運用深度優先搜尋法，完 成這道題目。我們先建立一個8*8格的棋盤，在棋盤的第一行的任意位置安放一隻皇后。緊接著，我們就來放 第二行，第二行的安放就要受一些限制了，因為與第一行的皇后在同一豎行或同一對角線的位置上是不能安放 皇后的，接下來是第三行，……，或許我們會遇到這種情況，在擺到某一行的時候，無論皇后擺放在什麼位 置，她都會被其他行的皇后吃掉，這說明什麼呢？這說明，我們前面的擺放是失敗的，也就是說，按照前面 的皇后的擺放方法，我們不可能得到正確的解。那這時怎么辦？改啊，我們回到上一行，把原先我們擺好的 皇后換另外一個位置，接著再回過頭擺這一行，如果這樣還不行或者上一行的皇后只有一個位置可放，那怎 么辦？我們回到上一行的上一行，這和老鼠碰了壁就回頭是一個意思。就這樣的不斷的嘗試，修正,我們最終會得到正確的結論的。
