L9_图和搜索(拓扑,DFS,BFS)
避免依赖递归传递统计:递归的本质是“扩展搜索”,而非“传递统计责任”。
记忆技巧
DFS:
"先处理自己,再管孩子":当前节点逻辑优先,邻居逻辑靠后。
想象DFS是自上而下的递归,必须先处理当前层。
BFS:
"进门先打卡,出门再干活":入队前标记防止重复,出队时处理实际逻辑。
想象BFS是逐层扩散,必须先保证节点唯一性。
visited
✅ 入队时标记
✅ 进入递归前标记
step 更新
✅ 出队时更新(当前层)
✅ 进入递归时 +1
是否回溯
❌ 不需要回溯(层序)
✅ 需要回溯(试探所有路径)
适合问题
最短路径、最小步数
所有路径、组合问题、连通性分析
数据结构
队列 queue
栈(递归 or 手动栈)
DFS集合
✅ DFS 中什么时候标记 visited
?
visited
?➤ 答案:进入递归时就标记 visited(也就是“下探”时)
DFS 中 step/distance 的更新时机?
➤ 答案:进入递归时可以顺带加一(类似路径深度)
for遍历时只有permutation的index是0开始,别的都是当前Pos开始
去重的时候,前后数相同直接跳过,对于Permutation II 遇到重复时候,前面数字用了,后面重复的数字才能用 ,这样可以防止【112】重复出现的情况。
DFS模板
def dfs(参数列表):
if 递归出口:
记录答案
return
for 所有的拆解可能性:
修改所有的参数
dfs(参数列表)
还原所有被修改过的参数
return something 如果需要的话,很多时候不需要 return 值除了分治的写法
BFS
“入队即访问,出队即处理” 意思是:我们在节点 入队时就当作访问过了(标记 visited),出队时才执行对应逻辑(打印、统计、等)。
一直需要判断
每次while+for loop,那个for loop为了得到当前层,word ladder2没用for loop,1有
BFS不回溯,DFS会
DFS不打算用回前面的字母,比如permutation,而是顺序向前的话,就用pos
用DFS解决的问题都可以用BFS
BFS按一层层来,适合有目标求最短路的步数,比如最小不熟,最少交换次数。层数就代表步数 word ladder。
因为BFS离根很近,所以遇到一个解一定是最优解,搜索可以停止。DFS要搜索完了才能知道最近的。
DFS用于连通性问题,容易爆栈。DFS不保存搜索状态,省空间。要搜索全部解用DFS省空间。
能用BFS就BFS,不行就DFS
二维数组N<20的,可用DFS
这里的bfs的q必须用deque 的popleft(), 或者 用 for loop。: timeplexity o(1)
不可用List,while和pop【0】,复杂度o(n)。
distance = {start_node: 0}
distance(dict) 有两个作用:
1 是记录一个点是否被丢进过队列了,避免重复访问
2 另外一个是记录 start_node 到其他所有节点的最短距离
如果只求连通性的话,可以换成 set 就行
node 做 key 的时候比较的是内存地址
# 如果需要返回所有点离起点的距离,就 return hashmap
return distance
# 如果需要返回所有连通的节点, 就 return HashMap 里的所有点
return distance.keys()
# 如果需要返回离终点的最短距离
return distance[end_node]
拓扑:
一定要判断 numCourses == len(q)!!!!!! Course Schedule II
三个元素,1个链表2个Map,图(邻接链表,像每个桶里装数组,arraylist的数组),入度(int[]或者map),q(queue或者arraylist,这里可能linkedlist可以所以arraylist也可以)
填充图,入度和Q。初始化图,就是遍历所有元素都建立一个对应链表。计算入度
入度为0的放入q里,将来遍历也是入度为0就进入bfs。或者都进入Q,然后for loop里每次入Q和出Q。
遍历q,把每个元素对应的链表再遍历
模板
alien dict
from heapq import *
class Solution:
"""
@param words: a list of words
@return: a string which is correct order
"""
def alienOrder(self, words):
# Construct Graph
in_degree = {ch: 0 for word in words for ch in word}
neighbors = {ch: [] for word in words for ch in word}
for pos in range(len(words) - 1):
for i in range(min(len(words[pos]), len(words[pos+1]))):
pre, next = words[pos][i], words[pos+1][i]
if pre != next:
in_degree[next] += 1
neighbors[pre].append(next)
break
# Topological Sort
heap = [ch for ch in in_degree if in_degree[ch] == 0]
heapify(heap)
order = []
while heap:
for _ in range(len(heap)):
ch = heappop(heap)
order.append(ch)
for child in neighbors[ch]:
in_degree[child] -= 1
if in_degree[child] == 0:
heappush(heap, child)
# order is invalid
if len(order) != len(in_degree):
return ""
return ''.join(order)
查环
有序用拓扑排序: BFS之后如果还有入度in degree > 0的,就有环。后面题目是入度为0就进入q,q.size() ==n 判断是否有环。
无序用并查集union find.
Bottom up 好像就是几个for loop的DP一点点加起来
Top down 就是递归或DFS,慢慢减,可以每次用数组或者Map记录中间结果,就变成记忆化。
BFS Python 快速写法
K是层数。这里q不pop,每次q都是该层,记得初始visited就要加入q
while K:
q = [i for j in q for i in m[j] if i not in seen]
seen |= set(q)
K -= 1
ballman
更新v-1次得到最短距离,比较慢。有负权值的使用它,否则就Dijkstra。 因为得到最优值要loop v-1次,该题要求k次,所以不一定有解。Cheapest Flights Within K Stops
Last updated
Was this helpful?