DFS模板
- 模板1
- 模板2
- 模板3
- 模板4
- 視頻講解
模板1
1
DFS(dep,...） //dep代表目前DFS的深度
{
if(找到解 || 走不下去){
... //在此處進行相應的操作
return ;
}
列舉下一種情況，DFS（dep+1,...）
}
模板2
2
int check(引數)
{
if(滿足條件)
return 1;
return 0;
}
void dfs(int step)
{
判斷邊界
{
相應操作
}
嘗試每一種可能
{
滿足check條件
標記
繼續下一步dfs(step+1)
恢復初始狀態（回溯的時候要用到）
}
}
模板3
3
/**
* 前置條件是visit陣列全部設定成false，visit[]標記是否已經訪問過
* @param n 當前開始搜索的節點
* @param d 當前到達的深度，也即是路徑長度
* @return 是否有解
*/
bool DFS(Node n, int d){
if (d == 4){//路徑長度為回傳true，表示此次搜索有解
return true;
}
for (Node nextNode in n){//遍歷跟節點n相鄰的節點nextNode，
if (!visit[nextNode]){//未訪問過的節點才能繼續搜索
//例如搜索到V1了，那么V1要設定成已訪問
visit[nextNode] = true;
//接下來要從V1開始繼續訪問了，路徑長度當然要加
if (DFS(nextNode, d+1)){//如果搜索出有解
//例如到了V6，找到解了，你必須一層一層遞回的告訴上層已經找到解
return true;
}
visit[nextNode] = false; //重新設定成未訪問，因為它有可能出現在下一次搜索的別的路徑中
}
//到這里，發現本次搜索還沒找到解，那就要從當前節點的下一個節點開始搜索，
}
return false;//本次搜索無解
}
模板4
4
void dfs(int step){
判斷邊界
嘗試每一種可能 for(i=1;i<=n;i++){
繼續下一步 dfs(step+1)
}
回傳
}
視頻講解
dfs視頻：嗶哩嗶哩
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/261782.html
標籤：區塊鏈
上一篇：vs控制臺使用入門