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. 终止条件一样len(path)==TARGET, res.append(list(path)), return
  2. API一样：dfs(nums, start, path, result, visited[optional]), 4个参数
    不同的是，组合模板是的下一轮递归用i + 1, 但这里由于是填位，一位一位加入，所以是start + 1

注意事项：

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

Python代码：

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

例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# char dfs (type 2 linear) Leetcode 77 Given two integers n and k, return all possible combinations of k numbers out of the range [1, n]
def combine(self, n: int, k: int) -> List[List[int]]:
	nums = [i + 1 for i in range(n)]
	path, res = [], []
	self.dfs2(nums, 0, k, [], res)
	return res

def dfs2(self, nums, start, k, path, res):
	if len(path) == k:
		res.append(list(path))
		return
	for i in range(start, len(nums)):
		path.append(nums[i])
		self.dfs2(nums, i + 1, k, path, res)
		path.pop()

填位法

跟字符型DFS/组合相同的地方：

  1. 终止条件一样len(path)==TARGET, res.append(list(path)), return
  2. API一样：dfs(nums, start, path, result, visited[optional]), 4个参数
    不同的是，组合模板是的下一轮递归用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 len(path) == TARGET: 
		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()

例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# filling dfs (type 3) LeetCode 017 Letter Combinations of a Phone Number 
def letterCombinations(self, digits: str) -> List[str]:
	if not digits:
		return []
	path, res = [], []
	self.dfs3(digits, 0, path, res)
	return res

def dfs3(self, digits, start, path, res):
	if len(path) == len(digits): # len(path) == TARGET
		res.append("".join(path))
		return
	keys = DIGIT2CHAR[digits[start]]
	for letter in keys:
		path.append(letter)
		self.dfs3(digits, start + 1, path, res) # remember start + 1
		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)

记忆性搜索(单边Catalan)

见记忆性搜索

例子：

LeetCode 140 Word Break II
这是单边catalan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
	wordSet = set()
	for word in wordDict:
		wordSet.add(word)
	cache = {}
	res = self.dfs(s, wordSet, cache)
	return [] if len(res) == 1 and not res[0] else res

def dfs(self, s, wordSet, cache):
	if not s:
		return ['']
	if s in cache:
		return cache[s]
	res = []
	for i in range(len(s)):
		if s[:i + 1] not in wordSet:
			continue
		li = self.dfs(s[i + 1:], wordSet, cache)
		for ss in li:
			res.append((s[:i + 1] + ' ' + ss).strip())

	cache[s] = res
	return res

例子：

返回结果是解的集合，所以终止条件返回也需要是一个[None]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# catelan dfs (type 4) LeetCode 095 Unique Binary Search Trees II
# return the root of all the possible trees
def generateTrees(self, n: int) -> List[TreeNode]:
	nums = [_ + 1 for _ in range(n)]
	return self.dfs4(nums, 0, n)

def dfs4(self, nums, start, end): # [start, end)
	if start >= end:
		return [None] # remember becaues we want the 2 for-loop happen
	res = []
	for i in range(start, end):
		left_root_nodes = self.dfs4(nums, start, i) # 0, 0
		right_root_nodes = self.dfs4(nums, i + 1, end) # 1, 1
		for left_root_node in left_root_nodes:
			for right_root_node in right_root_nodes:
				node = TreeNode(nums[i])
				node.left = left_root_node
				node.right = right_root_node
				res.append(node)
	return res

应用题型：

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