> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/l9tu-he-sou-suo.md).

# L9\_图和搜索(拓扑，DFS,BFS)

**避免依赖递归传递统计**：递归的本质是“扩展搜索”，而非“传递统计责任”。

#### **记忆技巧**

1. **DFS**：
   * **"先处理自己，再管孩子"**：当前节点逻辑优先，邻居逻辑靠后。
   * 想象DFS是**自上而下**的递归，必须先处理当前层。
2. **BFS**：
   * **"进门先打卡，出门再干活"**：入队前标记防止重复，出队时处理实际逻辑。
   * 想象BFS是**逐层扩散**，必须先保证节点唯一性。

| 特性      | BFS          | DFS             |
| ------- | ------------ | --------------- |
| visited | ✅ 入队时标记      | ✅ 进入递归前标记       |
| step 更新 | ✅ 出队时更新（当前层） | ✅ 进入递归时 +1      |
| 是否回溯    | ❌ 不需要回溯（层序）  | ✅ 需要回溯（试探所有路径）  |
| 适合问题    | 最短路径、最小步数    | 所有路径、组合问题、连通性分析 |
| 数据结构    | 队列 `queue`   | 栈（递归 or 手动栈）    |

### DFS集合

### ✅ DFS 中什么时候标记 `visited`？

#### ➤ 答案：**进入递归时就标记 visited（也就是“下探”时）**

### DFS 中 step/distance 的更新时机？

#### ➤ 答案：**进入递归时可以顺带加一（类似路径深度）**

### [combination sum、permutation、subset(组合和、全排列、子集)](https://www.cnblogs.com/xiaolovewei/p/8183246.html)

for遍历时只有permutation的index是0开始，别的都是当前Pos开始

去重的时候，前后数相同直接跳过，对于Permutation II 遇到重复时候，前面数字用了，后面重复的数字才能用 ，这样可以防止【112】重复出现的情况。

**DFS模板**

<pre class="language-python" data-title="" data-overflow="wrap"><code class="lang-python">def dfs(参数列表):

    if 递归出口:

<strong>        记录答案
</strong>        return

    for 所有的拆解可能性:

        修改所有的参数

        dfs(参数列表)

        还原所有被修改过的参数

    return something 如果需要的话，很多时候不需要 return 值除了分治的写法
</code></pre>

**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. 三个元素，1个链表2个Map，图(邻接链表，像每个桶里装数组，arraylist的数组），入度(int\[]或者map)，q(queue或者arraylist，这里可能linkedlist可以所以arraylist也可以）
2. 填充图，入度和Q。初始化图，就是遍历所有元素都建立一个对应链表。计算入度
3. **入度为0的放入q里，将来遍历也是入度为0就进入bfs。或者都进入Q，然后for loop里每次入Q和出Q。**

   遍历q，把每个元素对应的链表再遍历
4. 模板

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