KK's blog

每天积累多一些

0%

DFS

Posted on Edited on Disqus:

算法思路：

图用邻接表为输入，思路递归实现, 还要一个机制记录节点访问过没有，可以用HashSet，同时它作为结果存储BFS访问结果。
BFS多用于找最短路径
DFS多用于快速发现底部节点和具体路劲问题（如路径和或打印路径）。

BFS优缺点：
同一层的所有节点都会加入队列，所以耗用大量空间
仅能非递归实现
相比DFS较快，空间换时间
适合广度大的图

DFS优缺点：
无论是系统栈还是用户栈保存的节点数都只是树的深度，所以空间耗用小
有递归和非递归实现
由于有大量栈操作（特别是递归实现时候的系统调用），执行速度较BFS慢
适合深度大的图

如果BFS和DFS都可以用，建议用BFS，因为工业应用中，BFS不用有限的栈空间，可以利用到所有内存。

图DFS

算法步骤：

  1. 不合法情况（已访问、越界、trivial情况等）返回。
  2. 标记为已访问。
  3. 递归访问相邻节点。
  4. DFS路径尽量记录在数组中而非ArrayList中，路径(图)再DFS后要恢复为原状态L332。

Python代码：

1
2
3
4
5
6
7
def dfs(self, graph, start, visited, res):
	if start in visited:
		return
	visited.add(start)
	res.append(start)
	for node in graph[start]:
		self.dfs(graph, visited, node, res)

字符型DFS

注意事项：

  1. 输入值为空的情况或空节点
  2. 求得解以后复制path到result中
  3. 终止条件记得return
  4. 每次递归完恢复输入图或中间结果path的状态，递归式用i + 1

Python代码：

1
2
3
4
5
6
def dfs(self, input, start, endIndex, path, result): 
    if start == endIndex: 
        result.append(list(path))
        return 
    for i in <func>(input[start]): 
        self.dfs(input, i + 1, endIndex , path + input[i], result)

填位法

类似于排列(visited)，组合模板(带start)，组合模板是的下一轮递归用i + 1, 但这里由于是填位，一位一位加入，所以是start + 1

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def dfs(self, n, start, path, res, col_set):
	if start == n: # remember not len(path)
		res.append(list(path))
		return
	for i in range(n): 
		if not self.is_valid(start, i, col_set):
			continue
		path.append(i) 
		col_set.add(i)
		self.dfs(n, start + 1, path, res, col_set)
		col_set.remove(i)
		path.pop()

Catalan法(双边递归)

DFS中几乎是最难的类型。考得很少。主要思想是左右儿子递归结果叉乘，再将所有结果返回。所以返回值一定是list

注意事项：

  1. 返回结果是解的集合，所以终止条件返回也需要是一个list
  2. 循环中除掉自己，递归左部分和右半部分，叉乘它们的结果
  3. 与记忆性搜索的模板类似，有时需要和它一起用，见LeetCode 241 Different Ways to Add Parentheses

Python代码：

1
2
3
4
5
6
7
8
9
def dfs(self, input):
	if <终止条件>:
		return [] # remember to use list
	res = []
    for i in range(len(input)):
        left_res = self.dfs(input[:i])
        right_res = self.dfs(input[i + 1:])
        res += [<calculate results> for _l in left_res for _r in right_res]
	return res

时间复杂度Catalan数为O(C[n] += C[i-1]*C[n-i])，空间复杂度O(1)

应用题型：

LeetCode 095 Unique Binary Search Trees II
LeetCode 241 Different Ways to Add Parentheses

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
 * graph: 邻接表
 * visited: 记录已访问节点，避免重复访问
 * start: DFS的根节点
 */
public void dfs(HashMap<Integer, LinkedList<Integer>> graph, HashSet<Integer> visited, int start){
	if(visited.contains(start)){
		return;
	}
	visited.add(start);
	System.out.print(start+",");
	for(Integer child : graph.get(start)){
		dfs(graph, visited, child);
	}
}

算法分析：

时间复杂度为O(n)，h为树的高度，空间复杂度O(h)，如果用系统栈，可理解其为O(1)。

Free mock interview