①所謂深度搜索

深度優先搜索是一種在開發爬蟲早期使用較多的方法。它的目的是要達到被搜索結構的葉結點(即那些不包含任何超鏈的HTML文件) 。在一個HTML文件中，當一個超鏈被選擇后，被鏈接的HTML文件將執行深度優先搜索，即在搜索其余的超鏈結果之前必須先完整地搜索單獨的一條鏈。深度優先搜索沿著HTML文件上的超鏈走到不能再深入為止，然后返回到某一個HTML文件，再繼續選擇該HTML文件中的其他超鏈。當不再有其他超鏈可選擇時，說明搜索已經結束。

翻譯過來就是

深度優先搜索是一種需要遞歸算法為基礎的搜索方法，其遞歸邊界就是找到答案或此通道已到盡頭，則返回上一岔路口選擇另外一條沒有選擇過的路，以此類推。

如圖所示，就像樹分出的枝杈一樣。

之前考試的最后三題就需要DFS來解決

http://ybt.ssoier.cn:8088/problem_show.php?pid=1199

https://www.luogu.com.cn/problem/P1706

https://www.cnblogs.com/TFLSc1908lzs/p/13535504.html
————————————————————————————————————————————————————————————————————————————————————————
②算法過程

1.從根節點開始

2.放入一個節點（起始時放入的為根節點）

3.如果這個節點是第一次出現，則放入堆棧中

4.判斷該節點的子節點是否搜索完成，

a.如果是則將該節點出棧,判斷該棧是否為空

a.1 若為空則結束

a.2 若不為空則取棧頂元素，并回到第2步

b.如果沒有完成搜索，取未被搜索的根節點，并回到第2步

③例題代碼

全排列代碼

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n,a[25];
 4 void dfs(int deep){//deep表示當前深度（已經經過幾個岔路口
 5     if(deep==n+1){//遞歸邊界，表示路到盡頭
 6         for(int i=1;i<=n;i++)cout<<a[i]<<" ";//輸出當前順序
 7         cout<<endl;
 8         return;//返回上一岔路口
 9     }
10     for(int i=1;i<=n;i++){
11             a[deep]=i;//記錄此岔路口選擇
12             dfs(deep+1);//下一個岔路口
13     }
14 }
15 int main()
16 {
17     cin>>n;
18     dfs(1);
19     return 0;
20 }

結果如圖

總結

以上是生活随笔為你收集整理的深度优先搜索（DFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。