DFS深度优先搜索算法总结

发表于 | 分类于

总结复习一下DFS算法。

深度优先算法是N种算法的基础，是算法学习中的重中之重。

可以解决的问题类型也很多：递归，回溯，隐图式搜索，甚至是暴力类型算法的万金油。

DFS intro

图的深度优先搜索(Depth First Search)，和树的先序遍历比较类似。

它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

显然，深度优先搜索是一个递归的过程。

Understand DFS

无向图(undirected graph)

对于上图的遍历，步骤如下：

第1步：访问A。

第2步：访问(A的邻接点)C。 

在第1步访问A之后，接下来应该访问的是A的邻接点，即"C,D,F"中的一个。但在本文的实现中，顶点ABCDEFG是按照顺序存储，C在"D和F"的前面，因此，先访问C。

第3步：访问(C的邻接点)B。 

在第2步访问C之后，接下来应该访问C的邻接点，即"B和D"中一个(A已经被访问过，就不算在内)。而由于B在D之前，先访问B。

第4步：访问(C的邻接点)D。 

在第3步访问了C的邻接点B之后，B没有未被访问的邻接点；因此，返回到访问C的另一个邻接点D。

第5步：访问(A的邻接点)F。 

前面已经访问了A，并且访问完了"A的邻接点B的所有邻接点(包括递归的邻接点在内)"；因此，此时返回到访问A的另一个邻接点F。

第6步：访问(F的邻接点)G。

第7步：访问(G的邻接点)E。

因此访问顺序是：A -> C -> B -> D -> F -> G -> E

有向图(directed graph)

第1步：访问A。

第2步：访问B。 

在访问了A之后，接下来应该访问的是A的出边的另一个顶点，即顶点B。

第3步：访问C。 

在访问了B之后，接下来应该访问的是B的出边的另一个顶点，即顶点C,E,F。在本文实现的图中，顶点ABCDEFG按照顺序存储，因此先访问C。

第4步：访问E。 

接下来访问C的出边的另一个顶点，即顶点E。

第5步：访问D。 

接下来访问E的出边的另一个顶点，即顶点B,D。顶点B已经被访问过，因此访问顶点D。

第6步：访问F。 

接下应该回溯"访问A的出边的另一个顶点F"。

第7步：访问G。

因此访问顺序是：A -> B -> C -> E -> D -> F -> G

DFS implement

由于tree可以看做特殊的graph，这里针对graph来实现

​

1
2
3
4
public calss GraphNode{
  int val;
  List<GraphNode> neighnors;
}

为了防止重复，使用一个HashSet来保存已经遍历过的节点

​

1
HashSet<GraphNode> visited = new HashSet<GraphNode>();

Recursive DFS

每到一个节点，标记已经被访问过，对邻居里没有访问的节点进行DFS

1
2
3
4
5
6
7
8
9
public void DFS(GraphNode nd){
  //print nd.val
  visited.add(nd);
  for(GraphNode next : nd.neighbours){
    if(!visited.contains(next)){
      DFS(next);
    }
  }
}

经典的DFS，回溯算法(backtracking)其实相当于在一个求解域做DFS(剪枝)，另外，拓扑排序也是基于递归DFS进行的一点修改

Non-Recursive DFS

非递归版本，相比递归版本效率高，且不会导致栈溢出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void DFS(GraphNode start){
  Stack<GraphNode> s = new Stack<GraphNode>();
  q.push(start);
  visited.add(start);
  while(!s.empty()){
    GraphNode cur = s.pop();
    //print cur.val
    for(GraphNode next : cur.children){
      if(!visited.contains(next)){
        s.push(next);
        visited.add(next);//mark node as visited when adding to stack.
      }
    }
  }//while end
}

(for Tree) DFS with depth

深度在搜索中记录，递归版本加一个depth参数++就可以了，非递归版本用一个和s平行的栈记录深度

DFS for binary tree–PreOrder traversal

DFS对于二叉树而言，其遍历序列就是其前序遍历。

1
[preorder(node)] = node.val + [preorder(node.left)] + [preorder(node.right)]

Cycle Detection

对DFS稍作修改，可以判断一个有向图是否有回路

在递归版本里，我们队每一个点改为三种标记：

  • 未访问过(0)
  • 正在访问其邻居节点(1)
  • 已经访问完毕该节点以及所有该节点可以到达的节点(2)

什么时候会出现回路？就是当前节点v的一个邻居u的状态为1的时候。

因为该节点状态为1，即还没有把它以后的节点全部遍历，所以当前节点v肯定可以从u到达，而现在又可以从v到达u，所以回路构成。

为了表示一个节点的三种状态, 我们把visited的定义改一下, 定义为一个hashmap:
HasheMap visited = new HasheMap();

节点不在visited表示还未访问过, 节点对应为false表示正在访问, 节点对应为true表示已经访问该节点以及所有可以从它到达的节点.

1
2
3
4
5
6
7
8
9
10
public void DFS(GraphNode nd){      
    visited.put(nd, false); // mark as status-1   
    for(GraphNode next: nd.neighbors){   
        if( !visited.contains(next) )   
            DFS(next);   
        else if(visited.get(next)==false) // found cycle   
            System.out.println("Cycle detected!!!");   
    }// now all touchable nodes from nd are visited   
    visited.put(nd, true); // mark as status-2   
}

Topology Sort

这一节(以及上一节)参考这个非常棒的视频: https://class.coursera.org/algo-003/lecture/52

拓扑排序是一个dfs的应用, 所谓拓扑排序是指在一个DAG(有向无回路图)里给每个节点定义一个顺序(v1…vn), 使得按照这个顺序遍历的节点, 每一个节点vi都是之前遍历过的的节点(v1 ~ vi-1)所指向的(或没有任何其他节点指向的).

好像还没说清楚… 拓扑排序的一个应用就是对于各种依赖性(比如学习课程A需要先学习过课程B)组成的图寻找一个节点遍历的顺序使其可行.

propositions:

  • 拓扑排序的结果不唯一.
  • 有回路的图不存在拓扑顺序.
  • 如果一个节点没有出边, 那么它可以放在拓扑排序的最后面(没有节点以来它).
  • 如果一个节点没有入边, 那么它可以放在拓扑排序的最后面.

简单修改一下递归的dfs就可以处理拓扑排序: 维护一个计数器K(初始化为n=所有节点数), 每当一个点已经遍历完毕(所有通过这个点可以到达的点都已经被走过)以后, 就把这个点的顺序设为K, 同时减少K.

就用一个HashMap来为每个节点关联一个序号好了:
HasheMap order = new HasheMap();

1
2
3
4
5
6
7
public void DFS(GraphNode nd){      
    for(GraphNode next: nd.neighbors){   
        if( !visited.contains(next) )   
            DFS(next);   
    }// all touchable nodes from nd are visited   
    order.put(nd, K--);   
}

上面只是对于一个点进行的, 为了给所有点拓扑排序, 只要从一个没有出边的节点出发进行遍历, 一直运行到所有的节点都已经访问过为止。

LeetCode DFS

LeetCode上很多题目都是使用DFS或其思想进行处理的

DFS的框架可以理解为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//结果集
public static T ans = new T();
//中间结果集
public static T path = new T();
//问题
public static T problem(){
  ans.clear();//leetcode的一个特殊点，每次要清空结果集，避免重复
  robot(idx ,...);//DFS部分，常用idx作为结果递归的标志
  return ans;
}
//DFS
public static void robot(int idx, ...){
  if(xxx){//边界条件，递归出口条件
    //用当前path内容生成一部分结果集
    //handle path 
    ans.add(tmp);
    return;
  }
  //递归处理
  path[idx] = true;//递归前假设
  robot(++idx, ...);//根据不同情况进行处理
  path[idx] = false;//递归后还原
}

这里举例进行分析：

Subsets

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

1
2
3
4
5
6
7
8
9
10
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

原集合每一个数字只有两种状态，要么存在，要么不存在，那么在构造子集时就有选择和不选择两种情况，所以可以构造一棵二叉树，左子树表示选择该层处理的节点，右子树表示不选择，最终的叶节点就是所有子集合，树的结构如下：

DFS几乎可以算是图与树种最重要的算法，这里总结不算全面，但基本涵盖，这里最主要是搜索递归的思想。