一、深度優先搜索是什么
在一個求解問題答案的程序中，有幾種求解的方法，最為暴力的就是列舉法，列舉法列舉每一個答案即會產生一個狀態，這些狀態就會構成一棵解答樹，當然，對于大多數題目而言，這些狀態大多是無用的，這也就決定了列舉法的低效，
那么，難道就沒有方法進行優化了嗎？
答案是有的，因為列舉法產生了太多無用狀態，所以我們就應該從解答樹中去除這些無用的狀態，這種方法被稱作剪枝，搜索就是剪枝的一種方法，
既然弄清楚了什么是搜索，那么深度優先搜索又是什么呢？
上文介紹了解答樹的概念，我們知道，遍歷一棵樹有兩種方式，一種為層次遍歷（通常也被稱為廣度 / 寬度優先遍歷）；另一種為遞回遍歷（通常也被稱為深度優先遍歷），于是可以得到，遞回遍歷解答樹的方法被稱為深度優先搜索，而層次遍歷解答樹的方法被稱為廣度 / 寬度優先搜索，
二、深度優先搜索的應用題型
深度優先搜索的應用非常廣泛 （也被稱為騙分神器），大多數暴力列舉的題目都可以用深度優先搜索來優化，另外，還有一些問題需要使用回溯法，這種題型非常適合用深度優先搜索來完成，
三、深度優先搜索偽代碼
void dfs(一些必要的引數) { // 深搜英文縮寫為 dfs
if (到達遞回終點) {
比較是否為最優解
return;
}
進行一些操作
dfs(引數); // 進行下一輪搜索
}
四、例題
洛谷 P1706 全排列問題
這是一道非常簡單的深搜應用，代碼如下
bool vis[N]; // 訪問標記陣列
int a[N]; // 排列陣列，按順序儲存當前搜索結果
void dfs(int step) {
if (step == n + 1) { // 邊界
for (int i = 1; i <= n; i++) {
cout << setw(5) << a[i];
}
cout << endl;
return;
}
for (int i = 1; i <= n; i++) {
if (vis[i] == 0) {
vis[i] = 1;
a[step] = i;
dfs(step + 1);
vis[i] = 0;
}
}
return;
}
// 代碼來自 OI-Wiki
參考資料：
- 劉汝佳 《演算法競賽入門經典》
- OI Wiki 深度優先搜索
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/285770.html
標籤：其他