https://wiki.taigi.ima.org.tw/w/index.php?action=history&feed=atom&title=%E6%B7%B1%E5%BA%A6%E5%84%AA%E5%85%88%E6%90%9C%E6%8F%A3
深度優先搜揣 - 修訂紀錄
2026-05-23T14:23:13Z
本 wiki 上此頁面的修訂紀錄
MediaWiki 1.43.1
https://wiki.taigi.ima.org.tw/w/index.php?title=%E6%B7%B1%E5%BA%A6%E5%84%AA%E5%85%88%E6%90%9C%E6%8F%A3&diff=447090&oldid=prev
TaiwanTonguesApiRobot：從 JSON 檔案批量匯入
2025-08-23T01:24:47Z
<p>從 JSON 檔案批量匯入</p>
<p><b>新頁面</b></p><div>'''深度優先搜揣演算法'''（英語：Depth-First-Search，DFS）是一種用佇遍歷抑是搜尋樹仔抑是圖的演算法。這个演算法會冗早深的所在揣樹仔的分支。做節點 v 的所在邊攏去予人探揣過，搜揣欲回溯到發現節點 v 的彼條邊的起始節點。這个過程一直進行到已經發現對源節點會當到的所有節點為止。若猶閣存在無去予人發現的節點，則選擇其中一个作為源節點並重複以上的過程，規个行程重複進行一直到所有的點攏予人儉取做止。這款的演算法袂根據圖的結構等資訊調整執行策略。<br />
<br />
深度優先搜揣是圖論中的經典演算法，利用深度優先搜揣演算法會當產生目標圖的拓撲排序表，利用拓撲排序表會當方便解決真濟相關的圖論問題，如無權上長路徑問題等等。<br />
<br />
因發明「深度優先搜揣演算法」，約翰 ・ 霍普克洛夫特佮羅伯特 ・ 塔揚佇一九八六年共同得著電腦領域的上懸獎：圖靈獎。<br />
<br />
==演算方法==<br />
<br />
一 . 首先共根節點囥入去 stack 中。<br />
二 . 對 stack 中取出第一个節點，而且檢驗伊敢是目標。<br />
<br />
<br />
: 若揣著目標，結束搜揣並回傳結果。<br />
<br />
<br />
: 若無共伊某一个猶未檢驗過的直接子節點加入 stack 中。<br />
三 . 重複步數字。<br />
四 . 若是無存在無檢測過直接子節點。<br />
<br />
<br />
: 共頂一級節點加入 stack 中。<br />
<br />
<br />
: 重複步數字。<br />
五 . 重複步數四。<br />
六 . 若是 stack 為空，表示規張圖攏檢查過矣—— 亦即圖當中伊無欲走揣的目標。結束搜揣並回傳「揣無目標」。<br />
<br />
==C + + 的實作==<br />
<br />
定義一个結構體來表達一个二箍樹的節點的結構：<br />
<br />
若按呢咱咧走揣一个樹仔的時陣，佇一个節點開始，會當代先取得的是伊的兩个子節點。比如講：<br />
<br />
A 是第一个存取的，然後順序是 B 和 D、然後是 E。閣再來 C、F、G。按呢咱按怎來保證這个順序咧？<br />
<br />
遮就應該用疊起來的結構，因為疊一个是後進先出 ( LIFO ) 的順序。通過使用 C + + 的 STL，下跤的程式會當幫助理解：<br />
<br />
==參考文獻==<br />
<br />
==參見==<br />
<br />
* 闊度優先搜揣<br />
<br />
[[分類: 待校正]]</div>
TaiwanTonguesApiRobot