深度優先搜索

維基百科,自由的百科全書
前往: 導覽搜尋
深度優先搜索
節點搜索的順序
節點進行深度優先搜索的順序
概況
類別: 搜索演算法
資料結構:
時間複雜度:
空間複雜度:
最佳解:
完全性:
其他: b - 分支係數
m - 圖的最大深度

深度優先搜索算法英語:Depth-First-Search,簡稱DFS)是一種用於遍歷或搜索算法。沿著樹的深度遍歷樹的節點,儘可能深的搜索樹的分支。當節點v的所在邊都己被探尋過,搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點,則選擇其中一個作為源節點並重複以上過程,整個進程反覆進行直到所有節點都被訪問為止。屬於盲目搜索。

深度優先搜索是圖論中的經典算法,利用深度優先搜索算法可以產生目標圖的相應拓撲排序表,利用拓撲排序表可以方便的解決很多相關的圖論問題,如最大路徑問題等等。

因發明「深度優先搜索算法」,約翰·霍普克洛夫特羅伯特·塔揚共同獲得計算機領域的最高獎:圖靈獎[來源請求]

實現方法[編輯]

1. 首先將根節點放入隊列中。

2. 從隊列中取出第一個節點,並檢驗它是否為目標。

如果找到目標,則結束搜尋並回傳結果。

否則將它某一個尚未檢驗過的直接子節點加入隊列中。

3. 重複步驟2。

4. 如果不存在未檢測過的直接子節點。

將上一級節點加入隊列中。

重複步驟2。

5. 重複步驟4。

6. 若隊列為空,表示整張圖都檢查過了——亦即圖中沒有欲搜尋的目標。結束搜尋並回傳「找不到目標」。

C++的實現[編輯]

定義一個結構體來表達一個NODE的結構:

struct Node 
{
   int self; //数据 
   Node *left; //左节点 
   Node *right; //右节点 
};

那麼我們在搜索一個樹的時候,從一個節點開始,能首先獲取的是它的兩個子節點。例如:

A是第一個訪問的,然後順序是B和D、然後是E。然後再是C、F、G。那麼我們怎麼來保證這個順序呢?

這裡就應該用堆疊的結構,因為堆疊是一個先進後出的順序。通過使用C++STL,下面的程序能幫助理解:

 
const int TREE_SIZE = 9;
std::stack<Node*> unvisited; 
Node nodes[TREE_SIZE]; 
Node* current;

//初始化树
for(int i=0; i<TREE_SIZE; i++)
{
  nodes[i].self = i;
  int child = i*2+1;
  if(child<TREE_SIZE) // Left child
    nodes[i].left = &nodes[child];
  else
    nodes[i].left = NULL;
  child++;
  if(child<TREE_SIZE) // Right child    
    nodes[i].right = &nodes[child];
  else
    nodes[i].right = NULL;
}           

unvisited.push(&nodes[0]); //先把0放入UNVISITED stack

// 只有UNVISITED不空
while(!unvisited.empty())
{
  current=(unvisited.top()); //当前应该访问的
  unvisited.pop(); 
  if(current->right!=NULL) 
    unvisited.push(current->right); // 把右边压入 因为右边的访问次序是在左边之后
  if(current->left!=NULL) 
    unvisited.push(current->left);
  cout<<current->self<<endl;
}

參見[編輯]