[算法日志]圖論： 深度優(yōu)先搜索(DFS)
深度優(yōu)先概論
? 深度優(yōu)先搜索算法是一種遍歷圖這種數(shù)據(jù)結(jié)構(gòu)的算法策略，其中心思想是朝圖節(jié)點(diǎn)的一個方向不斷跳轉(zhuǎn)，當(dāng)該節(jié)點(diǎn)無下一個節(jié)點(diǎn)或所有方向都遍歷完時，便回溯朝上一個節(jié)點(diǎn)的另一個方向繼續(xù)遍歷。這種搜索策略與回溯法有異曲同工之妙。
DFS的代碼框架
void dfs(參數(shù))
{
if(終止條件)
{
儲存結(jié)果;
return;
}
for(遍歷節(jié)點(diǎn)的各個分支)
{
處理節(jié)點(diǎn)；
dfs(參數(shù));//調(diào)用本函數(shù)
撤銷處理，回溯；
}
}
正因為和回溯法有相似之處，所以其在代碼結(jié)構(gòu)上與回溯大致相同。
深搜三部曲
-
確認(rèn)遞歸函數(shù)及其參數(shù)
? 在深搜過程中，我們通常會定義兩個數(shù)組容器，一個二維數(shù)組儲存結(jié)果，一個一維數(shù)組儲存節(jié)點(diǎn)路徑。
? 而遞歸函數(shù)參數(shù)我們往往無法在一開始便確認(rèn)，通常都是在書寫遞歸邏輯時按需添加。
-
確認(rèn)終止條件
? 終止條件的不同有時會導(dǎo)致函數(shù)的需要遍歷的值不同。同時，遞歸條件如果確定錯誤會導(dǎo)致死循環(huán)，棧溢出等錯誤。所以確定好遞歸條件是比較關(guān)鍵的一步。
-
遍歷節(jié)點(diǎn)的各個路徑
首先將本節(jié)點(diǎn)下一個要遍歷的節(jié)點(diǎn)放進(jìn)路徑，適當(dāng)處理后進(jìn)入遞歸函數(shù)，回來時將該節(jié)點(diǎn)從路徑中取出，做回溯操作。文章來源：http://www.zghlxwxcb.cn/news/detail-775364.html
深搜的簡單應(yīng)用
leetcode 797
示例代碼文章來源地址http://www.zghlxwxcb.cn/news/detail-775364.html
void DFS1(const vector<vector<int>>& mygraph, vector<vector<int>>& result, vector<int>& path, int next)
{
if (mygraph[next].empty() || path.back() == mygraph.size() - 1)
{
if (path.back() == mygraph.size() - 1)
result.push_back(path);
return;
}
const int size = mygraph[next].size();
for (int i = 0; i < size; ++i)
{
path.push_back(mygraph[next][i]);
DFS1(mygraph, result, path, mygraph[next][i]);
path.pop_back();
}
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& mygraph)
{
vector<vector<int>> result;
vector<int> path;
if (mygraph.empty())
return result;
path.push_back(0);
DFS1(mygraph, result, path, 0);
return result;
}
到了這里，關(guān)于[算法日志]圖論： 深度優(yōu)先搜索(DFS)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
