dfs搜索演算法

A. 基本演算法——深度優先搜索（DFS）和廣度優先搜索（BFS）

        深度優先搜索和廣度優先搜索，都是圖形搜索演算法，它兩相似，又卻不同，在應用上也被用到不同的地方。這里拿一起討論，方便比較。

一、深度優先搜索

        深度優先搜索屬於圖演算法的一種，是一個針對圖和樹的遍歷演算法，英文縮寫為DFS即Depth First Search。深度優先搜索是圖論中的經典演算法，利用深度優先搜索演算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。一般用堆數據結構來輔助實現DFS演算法。其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次。

基本步奏

（1）對於下面的樹而言，DFS方法首先從根節點1開始，其搜索節點順序是1,2,3,4,5,6,7,8（假定左分枝和右分枝中優先選擇左分枝）。

（2）從stack中訪問棧頂的點；

（3）找出與此點鄰接的且尚未遍歷的點，進行標記，然後放入stack中，依次進行；

（4）如果此點沒有尚未遍歷的鄰接點，則將此點從stack中彈出，再按照（3）依次進行；

（5）直到遍歷完整個樹，stack里的元素都將彈出，最後棧為空，DFS遍歷完成。

二、廣度優先搜索

        廣度優先搜索（也稱寬度優先搜索，縮寫BFS，以下採用廣度來描述）是連通圖的一種遍歷演算法這一演算法也是很多重要的圖的演算法的原型。Dijkstra單源最短路徑演算法和Prim最小生成樹演算法都採用了和寬度優先搜索類似的思想。其別名又叫BFS，屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止。基本過程，BFS是從根節點開始，沿著樹(圖)的寬度遍歷樹(圖)的節點。如果所有節點均被訪問，則演算法中止。一般用隊列數據結構來輔助實現BFS演算法。

基本步奏

（1）給出一連通圖，如圖，初始化全是白色（未訪問）；

（2）搜索起點V1（灰色）；

（3）已搜索V1（黑色），即將搜索V2，V3，V4（標灰）；

（4）對V2，V3，V4重復以上操作；

（5）直到終點V7被染灰，終止；

（6）最短路徑為V1，V4，V7.

B. dfs演算法是什麼

dfs演算法是深度優先搜索。

深度優先搜索屬於圖演算法的一種，英文縮寫為DFS。其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次。

深度優先搜索是一種在開發爬蟲早期使用較多的方法，它的目的是要達到被搜索結構的葉結點（即那些不包含任何超鏈的HTML文件）。

主要思想

借用一個鄰接表和布爾類型數組（判斷一個點是否查看過，用於避免重復到達同一個點，造成死循環等），先將所有點按一定次序存入鄰接表，再通過迭代器，對鄰接表的linklist和布爾數組做出操作，從而達到不重復遞歸遍歷的效果。

C. dfs演算法是什麼

DFS其實叫深度優先搜索演算法，起始它只是一種搜索的方法思路，並沒有固定的演算法格式。

作為搜索演算法的一種，DFS對於尋找一個解的NP（包括NPC）問題作用很大。但是，搜索演算法畢竟是時間復雜度是O(n!)的階乘級演算法，它的效率非常低，在數據規模變大時，這種演算法就顯得力不從心了。

DFS思路：

DFS思路是一條路走到底，撞到了牆再回頭。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重復以上過程，整個進程反復進行直到所有節點都被訪問為止，屬於盲目搜索。

D. dfs演算法是什麼

DFS是深度優先搜索演算法。

深度優先搜索演算法，又稱DFS(Depth First Search)。DFS演算法是一種搜索演算法，而搜索演算法實質上是一種枚舉，即藉助計算機的高性能來有目的地枚舉一個問題的部分情況或這個問題的所有情況，進而求出問題的解的一種方法。

分類：

1、 順序性剪枝

若一些題的搜索順序對答案無影響，那麼搜索順序的不同會導致搜索樹形態的改變，優先搜索分支較少的階段，此時能減少搜索的規模。

2、 重復性剪枝

在搜索的時候如果有多種方式可以到達一個狀態，那麼只需要搜索一個分支就可以了。

3、 可行性剪枝

可行性剪枝是對搜索正確性的一個保證，當分支在遞歸邊界的時候回溯。