dfs,bfs

https://www.jianshu.com/p/a753d5c733ec

dfs

1 递归实现

1
2
3
def dfs(当前节点,子节点)
for node in 子节点
dfs(node,new 子节点)

310. 最小高度树

1
2
#### root 当前节点 path子节点 depth 深度
dfs(root,path,depth)

695. 岛屿的最大面积

1
2
###grid全部格点 cur_i,cur_j 当前节点的位置,用+1-1可以确定子节点
dfs(self, grid, cur_i, cur_j) :

2 迭代实现

bfs

1 迭代实现

root进队,root出队,root的子节点【a,b,c】进队,a出队,a的子节点进队,b出队,b的子节点进队。。。

访问顺序(出队顺序):root a b c 。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
if root==None:
return []
ans = []
q = [root]
while q:
# length = len(q)
# arr = []
# for _ in range(length):
node = q.pop(0)
# arr.append(node.val)
for chd in node.children:
q.append(chd)
# if arr:
ans.append(node.val)
return ans

429. N 叉树的层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
ans = [] ##结果
q = [root] ##队列
while q:
length = len(q)
arr = [] #出队
for _ in range(length):
node = q.pop(0)
if not node:
continue
arr.append(node.val)
for chd in node.children:
q.append(chd)
if arr:
ans.append(arr)
return ans

2 递归实现

应用选择

时间复杂度都为O(n),n为全部节点

  1. BFS是用来搜索最短径路的解是比较合适的,比如求最少步数的解,最少交换次数的解,因为BFS搜索过程中遇到的解一定是离根最近的,所以遇到一个解,一定就是最优解,此时搜索算法可以终止。这个时候不适宜使用dfs,因为DFS搜索到的解不一定是离根最近的,只有全局搜索完毕,才能从所有解中找出离根的最近的解。(当然这个DFS的不足,可以使用迭代加深搜索ID-DFS去弥补)
  2. DFS适合搜索全部的解,而正因为要搜索全部的解,那么BFS搜索过程中,遇到离根最近的解,并没有什么用,也必须遍历完整棵搜索树;DFS搜索会搜索全部,但是相比之下 DFS不用记录过多信息,所以搜素全部解的问题,DFS显然更加合适。空间优劣上,DFS是有优势的,DFS不需要保存搜索过程中的状态,而BFS在搜索过程中需要保存搜索过的状态,而且一般情况需要一个队列来记录。

和回溯的关系

回溯是算法思想,dfs和bfs是搜索解空间的手段

参考

https://www.jianshu.com/p/e81a16a6f771

https://blog.csdn.net/weixin_41894030/article/details/95317440

Author

Lavine Hu

Posted on

2022-04-06

Updated on

2024-06-19

Licensed under

Comments

:D 一言句子获取中...