人工智慧/搜尋/啟發式搜尋/深度優先搜尋
深度優先搜尋是一種用於查詢以圖形格式表示的資訊的演算法。深度優先搜尋的第一個版本，最初被稱為 Tremaux 演算法，是在 19 世紀被設計為解決迷宮的一種方法（Stewart，1999）。然而，“Tremaux 迷宮求解方法的理論特性”直到 1970 年才在計算機科學領域被發現，當時 John Hopcroft 和 Robert Tarjan 合作使用深度優先搜尋來“獲得線性時間演算法”（Tarjan，1972，第 146 頁）。
演算法，這個詞最初是由數學家穆罕默德·伊本·穆薩·花拉子米在公元 8 世紀後期創造的，指的是用於找到問題解決方案的程式或公式（Berardi、Kroon、McDermott 和 Newton，2006）。演算法使用各種輸入；這些輸入通常包含的資訊量不同。一個好的演算法必須能夠有效地將任何長度的輸入組織成基本的功能步驟，這些步驟可以儲存在程式的記憶體中（“PC”，2008）。Hopcroft 和 Trajan 的線性時間演算法使輸入的大小與程式解決特定問題所花費的資源和時間相等（Tarjan，1972）。
深度優先搜尋演算法用於垂直遍歷以樹狀結構格式化的圖形資訊節點。從圖形頂部的單個節點開始，搜尋從樹狀結構的最左側開始，移動到每個後續節點，直到搜尋到達樹狀結構的最底部節點。在每個樹狀結構段上的每個節點的搜尋完成之前，搜尋不會從左到右水平移動（Siek & Lee，2000）。
深度優先搜尋最重要的功能之一是能夠跟蹤已經訪問過的節點。以下虛擬碼允許此功能。
DFS(u):
visit(u);
time = time + 1;
d[u] = time;
color[u] = grey;
for all nodes v adjacent to u do
if color[v] == white then
p[v] = u;
DFS(u);
time = time + 1;
f[u] = time;
color[u] = black;
由 Kravitz、David 和 Lafferty（1997）建立的這個虛擬碼展示了深度優先搜尋演算法如何透過有效地跟蹤已經訪問過的節點和仍然需要探索的節點來工作。Kravitz 等人將每個需要探索的節點設為白色，每個正在探索的節點設為灰色，每個已經探索過的節點設為黑色。節點的顏色編碼允許使用者跟蹤搜尋演算法的進度，以及保持一個準確的資料對映，顯示哪些節點已經被儲存。程式碼中的第一行初始化深度優先搜尋，從圖形中最左側的樹段開始。
DFS(u):
這段程式碼塊允許搜尋引擎訪問樹狀結構中最左側樹段上的每個節點，在搜尋每個節點一次時，將節點從白色變為灰色。
visit(u); time = time + 1; d[u] = time; color[u] = grey;
這段程式碼塊將搜尋水平地跨越樹狀結構，從左到右，一旦樹狀結構左側的每個節點都被搜尋過一次。換句話說，演算法會朝向白色節點移動。當演算法完成對某個節點的搜尋後，該節點會變為黑色，演算法不能再次搜尋該節點。
for all nodes v adjacent to u do
if color[v] == white then
p[v] = u;
DFS(u);
time = time + 1;
f[u] = time;
color[u] = black;
深度優先搜尋的一個實際應用是“用於確定圖形是否為平面的演算法”（“圖形”，2008）。基本上，平面圖形可以繪製在平面上，而不會使圖形邊緣交叉（Weisstein，2008）。深度優先搜尋使使用者能夠“透過樹[結構]的後序遍歷”來組織圖形中表示的資訊（“平面”，2008）。換句話說，深度優先搜尋使使用者能夠決定他們想要“嵌入反向邊”的順序，從第一個節點到每個後續節點。如果在此過程中，使用者確定某個節點組與當前未在樹狀結構圖形中表示的其他節點有潛在連線，那麼使用者就會知道該特定樹段必須“保持在平面圖形的外部面”（“平面”，2008）。
在深度優先搜尋中，“每個節點都與兩個時間相關聯：發現時間和完成時間”（Kravitz、David & Lafferty，1997）。如果搜尋引數很大（即大量節點），那麼“儲存所有這些時間所需的儲存空間”將很快變得難以管理（Kravitz、David & Lafferty，1997）。
- Berardi, R. R., Kroon, L. A., McDermott, J. H. & Newton, G. D. (2006). 非處方藥手冊. 美國藥劑師協會：華盛頓特區。
- 圖形遍歷. 檢索於 2008 年 10 月 14 日. http://www.mec.ac.in/resources/notes/notes/ds/gratra.htm
- Kravitz, R., David, R., & Lafferty, R. (1997). 檢索於 2008 年 10 月 14 日. http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic26/#dfs
- PC 雜誌. 檢索於 2008 年 10 月 14 日. http://www.pcmag.com/encyclopedia_term/0,2542,t=algorithm&i=37649,00.asp
- 平面圖. 檢索於 2008 年 10 月 14 日。
- Siek, J. & Lee, L. (2000). 檢索於 2008 年 10 月 14 日. http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/depth_first_search.html
- Stewart, I. (1999). 魔術迷宮：用數學的眼光看世界. John Wiley & Sons Inc: 紐約。
- Tarjan, R. E. (1972). 深度優先搜尋和線性圖演算法. SIAM J. 計算，1(2)，1972。
- Weisstein, E. W. “平面圖”. 來自 MathWorld - Wolfram 網頁資源. 檢索於 2008 年 10 月 14 日. https://mathworld.tw/PlanarGraph.html