深度優先搜尋（DFS：Depth-First Search）是一種圖搜尋政策，其将搜尋限制到 2 種操作：
(a) 通路圖中的一個節點；
(b) 通路該節點的子節點；
在深度優先搜尋中，對于最新發現的頂點，如果它還有以此為起點而未探測到的邊，就沿此邊繼續探測下去。當頂點 v 的所有邊都已被探尋過後，搜尋将回溯到發現頂點 v 有起始點的那些邊。這一過程一直進行到已發現從源頂點可達的所有頂點為止。實際上深度優先搜尋最初的探究也是為了解決迷宮問題。
對圖的深度優先搜尋與對樹（Tree）的深度優先周遊（Depth First Traversal）是類似的，差別在于圖中可能存在環，是以可能會周遊到已經周遊的節點。
例如，下面的圖中，從頂點 2 開始周遊，當周遊到頂點 0 時，子頂點為 1 和 2，而頂點 2 已經周遊過，如果不做标記，周遊過程将陷入死循環。是以，在 DFS 的算法實作中需要對頂點是否通路過做标記。
上圖的 DFS 周遊結果為 2, 0, 1, 3。
DFS 算法可以通過不同方式來實作：
遞歸方式
非遞歸方式：使用棧（Stack）資料結構來存儲周遊圖中節點的中間狀态；
DFS 算法的遞歸方式僞碼如下：
DFS 算法的非遞歸方式僞碼如下：
<a></a>
深度優先搜尋（DFS）的時間複雜度為 O(V+E)，V 即 Vertex 頂點數量，E 即 Edge 邊數量。
DFS 算法實作代碼如下：
<a href="http://www.cnblogs.com/gaochundong/p/breadth_first_search.html" target="_blank">廣度優先搜尋</a>
<a href="http://www.cnblogs.com/gaochundong/p/depth_first_search.html" target="_blank">深度優先搜尋</a>
<a href="http://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/" target="_blank">Breadth First Traversal for a Graph</a>
<a href="http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/" target="_blank">Depth First Traversal for a Graph</a>
<a href="http://www.cnblogs.com/taoziwel/articles/1855901.html" target="_blank">深度優先搜尋 廣度優先搜尋類訓練題</a>
<a href="http://courses.csail.mit.edu/6.006/spring11/lectures/lec13.pdf" target="_blank">Introduction to Algorithms 6.006 - Lecture 13</a>
<a href="http://iprai.hust.edu.cn/icl2002/algorithm/algorithm/commonalg/graph/traversal/dfs.htm" target="_blank">深度優先搜尋 DFS</a>
<a href="http://iprai.hust.edu.cn/icl2002/algorithm/algorithm/" target="_blank">算法與資料結構</a>
本文轉自匠心十年部落格園部落格，原文連結：http://www.cnblogs.com/gaochundong/p/depth_first_search.html，如需轉載請自行聯系原作者