# 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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/l9tu-he-sou-suo.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.