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模板
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)。
拓扑:
一定要判断 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
查环
有序用拓扑排序: 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
ballman
更新v-1次得到最短距离,比较慢。有负权值的使用它,否则就Dijkstra。 因为得到最优值要loop v-1次,该题要求k次,所以不一定有解。Cheapest Flights Within K Stops
Last updated
Was this helpful?