深度优先搜索

维基百科,自由的百科全书
跳转至: 导航搜索
深度优先搜索
節點搜索的順序
節點進行深度优先搜索的順序
概况
類別: 搜索演算法
資料結構:
時間複雜度:
空間複雜度:
最佳解:
完全性:
其他: b - 分支係數
m - 圖的最大深度

深度优先搜索算法英语:Depth-First-Search,简称DFS)是一种用于遍历或搜索算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如最大路径问题等等。

因发明“深度优先搜索算法”,約翰·霍普克洛夫特罗伯特·塔扬共同获得计算机领域的最高奖:图灵奖[來源請求][1]

主要思想[编辑]

主要思想:不撞南墙不回头。

深度优先遍历的主要思想就是:首先以一个未被访问过的顶点作为起始顶点,沿当前顶点的边走到未访问过的顶点;当没有未访问过的顶点时,则回到上一个顶点,继续试探访问别的顶点,直到所有的顶点都被访问。

沿着某条路径遍历直到末端,然后回溯,再沿着另一条进行同样的遍历,直到所有的顶点都被访问过为止。

图解[编辑]

http://img.my.csdn.net/uploads/201503/12/1426092118_7791.gif

分析[编辑]

通过上面的图例可以非常直观的了解深度优先搜索的工作方式。下面来分析一下如何用代码来实现它。 大家都知道,深度优先的主要思想就是“不撞南墙不回头”,“一条路走到黑”,如果遇到“墙”或者“无路可走”时再去走下一条路。

所以先规定好一个走路的规则,比如就按照右下左上顺时针的方式去尝试。

如上图僵尸的位置是起始点,先往右走,但是有堵墙走不了,所以按照规定尝试往下走。到达“1”的位置,此时重复刚才的步骤,先向右走可以走到“2”,再重复规则发现向右可以走到“3”,再重复发现“下右左上”四个方向都不能走,这时候就退回“2”的位置尝试向下走,依次类推直到走到最终的目的地。

聪明的你肯定已经发现了“递归”是实现深度优先搜索的最好的方式。定义好规则然后就这样递归的循环下去直到走到终点,请看下面的伪代码:

伪代码[编辑]

 1 void dfs()  
 2 {  
 3     // 判断是否到达终点
 4     if() {
 5         return;
 6     }
 7 
 8     // 尝试每一个可走方向(右下左上) 
 9     for(i=0; i<n; i++){ 
10         // 判断是否可走,可走调用递归尝试下一步,不可走则尝试该点的其他方向
11         if () {
12             // 继续下一步  
13             dfs();  
14         }
15     }  
16 }

c++代码[编辑]

// 深度优先搜索

 1     public void DFS( int x, int y )
 2         throws Exception
 3     {
 4 
 5         int tx, ty;
 6 
 7         int[] pos =
 8             { x, y };
 9         dfs_posList.add(pos);
10 
11         // 是否到达目的地
12         if (mMapView[y][x] == 8)
13         {
14             throw new Exception("find");
15         }
16 
17         // 顺时针循环,右下左上四个方向
18         for (int k = 0; k < 4; k++)
19         {
20             tx = x + next[k][1];
21             ty = y + next[k][0];
22 
23             // 是否出了边界
24             boolean isOut = tx < 0 || tx >= mapWidth || ty < 0 || ty >= mapHeight;
25             if (!isOut)
26             {
27 
28                 // 是否是障碍物
29                 if (mMapView[ty][tx] == 0 && dfs_book[tx][ty] == 0 || mMapView[ty][tx] == 8)
30                 {
31                     dfs_book[tx][ty] = 1;
32                     DFS(tx, ty);
33                     dfs_book[tx][ty] = 0;
34                 }
35             }
36 
37         }
38     }

// 判断方向的数组 int[][] next =

       {
               { 0, 1 }, // 右
               { 1, 0 }, // 下
               { 0, -1 }, // 左
               { -1, 0 } // 上
       };

实现方法[编辑]

1. 首先将根节点放入队列中。

2. 从队列中取出第一个节点,并检验它是否为目标。

如果找到目标,则结束搜寻并回传结果。

否则将它某一个尚未检验过的直接子节点加入队列中。

3. 重复步骤2。

4. 如果不存在未检测过的直接子节点。

将上一级节点加入队列中。

重复步骤2。

5. 重复步骤4。

6. 若队列为空,表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

C++的实现[编辑]

定义一个结构体来表达一個二元樹的节点的结构:

1 struct Node {
2     int self;     // 数据
3     Node *left;   // 左节点
4     Node *right;  // 右节点
5 };

那么我们在搜索一个树的时候,从一个节点开始,能首先获取的是它的两个子节点。例如:

A是第一个访问的,然后顺序是B和D、然后是E。然后再是C、F、G。那么我们怎么来保证这个顺序呢?

这里就应该用堆栈的结构,因为堆栈是一个先进后出的顺序。通过使用C++STL,下面的程序能帮助理解:

 1  
 2 const int TREE_SIZE = 9;
 3 std::stack<Node *> unvisited;
 4 Node nodes[TREE_SIZE];
 5 Node *current;
 6 
 7 //初始化树
 8 for (int i = 0; i < TREE_SIZE; i++) {
 9     nodes[i].self = i;
10     int child = i * 2 + 1;
11     if (child < TREE_SIZE) // Left child
12         nodes[i].left = &nodes[child];
13     else
14         nodes[i].left = NULL;
15     child++;
16     if (child < TREE_SIZE) // Right child
17         nodes[i].right = &nodes[child];
18     else
19         nodes[i].right = NULL;
20 }
21 
22 unvisited.push(&nodes[0]); //先把0放入UNVISITED stack
23 
24 // 只有UNVISITED不空
25 while (!unvisited.empty()) {
26     current = (unvisited.top()); //当前应该访问的
27     unvisited.pop();
28     if (current->right != NULL)
29         unvisited.push(current->right); // 把右边压入 因为右边的访问次序是在左边之后
30     if (current->left != NULL)
31         unvisited.push(current->left);
32     cout << current->self << endl;
33 }

参考文献[编辑]

  1. ^ Robert E Tarjan - A.M. Turing Award Winner. [2017-10-29] (English). 

參見[编辑]