# 搜索与图论模块讲义

本模块包含 **DFS、BFS、树与图的深度优先遍历、树与图的广度优先遍历、拓扑排序、Dijkstra、Bellman-Ford、SPFA、Floyd、Prim、Kruskal、染色法判定二分图、匈牙利算法** 共 13 个核心图论与搜索算法。

---

## 1. DFS (深度优先搜索 - Depth First Search)

### 核心思想与性格
* **性格**：不撞南墙不回头。
* **做法**：一条路走到黑。先选一条路一直往前走，走不通了（死胡同）就退回上一步（这叫**回溯**），换一条路再试，直到把所有的可能性全部搜完。通常使用**递归**实现。

### 经典应用：全排列问题
用 DFS 生成 $1 \sim n$ 的全排列：
```cpp
int path[N], st[N]; // path存当前路径，st记录哪个数字被用过了
void dfs(int u) {
    if (u > n) {
        for (int i = 1; i <= n; i++) cout << path[i] << " ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!st[i]) {
            st[i] = true; path[u] = i;
            dfs(u + 1);
            st[i] = false; // 回溯，恢复现场
        }
    }
}
```

---

## 2. BFS (广度优先搜索 - Breadth First Search)

### 核心思想与性格
* **性格**：稳扎稳打，层层推进。
* **做法**：像水波纹一样向四周一圈一圈扩散。先看离起点距离为 1 的所有点，再看距离为 2 的所有点……
* **特点**：通常使用**队列 (Queue)** 实现。在**边权全部相等（或无权图）**的情况下，BFS 搜索到目标时，走过的步数一定是最短路。

---

## 3. 树与图的深度优先遍历 & 4. 树与图的广度优先遍历

### 图的存储：邻接表
在计算机里，我们用**邻接表**来存图。每一个节点都有一个链表，记录它能直接走到哪些邻居。
```cpp
// h[N] 存每个点链表的头节点，e[] 存邻居是谁，ne[] 存下一条边
int h[N], e[M], ne[M], idx;

void add(int a, int b) { // 添加一条从 a 到 b 的有向边
    e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}
```

* **树的 DFS**：递归遍历每个节点的子树，常用于求树的深度、子树节点个数。
* **树的 BFS**：利用队列进行层序遍历，常用于求树的宽度或按层处理信息。

---

## 5. 拓扑排序 (Topological Sort)

### 核心思想
* **场景**：学校选课。想学《高等数学》必须先学《初等数学》。
* **拓扑排序**：把一张有向无环图（DAG）的所有节点排成一个线性序列，使得对图中的每一条有向边 $(u, v)$，$u$ 都排在 $v$ 的前面。
* **入度**：有几条边指向这个点。

### 算法步骤
1. 把所有**入度为 0** 的点（没有前置要求）放入队列。
2. 队头元素出队，把它指向的邻居的**入度减 1**。
3. 如果邻居的入度减到了 0，立刻把这个邻居也丢进队列。
4. 重复直到队列为空。如果最后所有点都被遍历到了，说明存在拓扑排序（图无环）。

---

## 6. Dijkstra 算法

### 作用与限制
* **作用**：求**单源最短路径**（从一个起点到其他所有点的最短距离）。
* **核心限制**：**图里面绝对不能有负权边**（否则贪心会失效）。
* **时间复杂度**：朴素版 $O(n^2)$，堆优化版 $O(m \log n)$。

### 贪心策略
每次从未确定最短路的点中，挑一个**离起点最近的点**，把它标记为“已确定”，然后用它去更新它所有邻居的距离（这叫**松弛操作**）。

```cpp
// 堆优化 Dijkstra 核心逻辑
priority_queue<PII, vector<PII>, greater<PII>> heap;
dist[1] = 0;
heap.push({0, 1}); // {距离, 点编号}

while (heap.size()) {
    auto t = heap.top(); heap.pop();
    int ver = t.second, distance = t.first;
    if (st[ver]) continue;
    st[ver] = true;

for (int i = h[ver]; i != -1; i = ne[i]) {
        int j = e[i];
        if (dist[j] > distance + w[i]) {
            dist[j] = distance + w[i];
            heap.push({dist[j], j});
        }
    }
}
```

---

## 7. Bellman-Ford 算法

### 作用与特点
* **作用**：求单源最短路，**允许图中有负权边**。
* **负权回路**：如果图中存在一个环，且环上的边权总和为负数，那么绕这个环转一圈距离就会变小无限次，最短路就不存在。Bellman-Ford 可以检测负权回路。
* **核心做法**：对所有的边进行 $n-1$ 次**松弛操作**。如果第 $n$ 次循环还能松弛，说明存在负环。

---

## 8. SPFA 算法 (Shortest Path Faster Algorithm)

### 核心思想
* **本质**：它是 Bellman-Ford 算法的**队列优化版**。
* **优化逻辑**：Bellman-Ford 每次盲目检查所有的边太慢了。SPFA 发现：只有当一个点的最短距离变小了，它才有资格去更新它的邻居。所以用一个队列把“距离变小了的点”存起来。在大多数没有负环的图里，SPFA 运行速度极快。

---

## 9. Floyd 算法

### 作用与精妙代码
* **作用**：求**多源汇最短路径**（图里任意两个点之间的最短距离），允许负权边，但不能有负环。
* **核心思想（动态规划）**：三层循环。外层枚举中转站 $k$（$1 \to n$），内层枚举起点 $i$ 和终点 $j$。如果通过 $k$ 中转能让路程变短，就更新它：
  $$d[i][j] = \min(d[i][j], d[i][k] + d[k][j])$$
* **代码极短**：
  ```cpp
  for (int k = 1; k <= n; k++)
      for (int i = 1; i <= n; i++)
          for (int j = 1; j <= n; j++)
              d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
  ```

---

## 10. Prim 算法

### 作用
求**最小生成树 (MST)**。给定一张带权连通图，用最少的边（刚好 $n-1$ 条）把所有点连起来，且所有边的总权值最小。
### 做法
Prim 算法和 Dijkstra 极其相似：
* Dijkstra 是求点到起点的距离，Prim 是求**点到当前生成树的距离**。
* 每次挑一个离生成树最近的点加入树中，并更新其他点到生成树的距离。

---

## 11. Kruskal 算法

### 作用与直观步骤
另一种求最小生成树的方法，代码简单且极其直观。
1. **排序**：把图中的所有边按照**权值从小到大**排序。
2. **挑选**：从小到大扫描每条边 $(u, v)$：
   * 用**并查集**判断 $u$ 和 $v$ 是否已经连通。
   * 如果不连通，说明没有成环，把这条边选入生成树，并将 $u$ 和 $v$ 合并。
   * 直到选够 $n-1$ 条边为止。

---

## 12. 染色法判定二分图

### 什么是二分图？
如果能把图中的所有点分成两个集合，使得图里所有的边都横跨在两个集合之间（同一个集合内部的点之间没有连线），这张图就是二分图。
### 做法（DFS / BFS）
遍历整张图，用两种颜色（比如 1 和 2）轮流涂色：
* 如果搜索到一个未涂色的邻居，把它涂成与当前点不同的颜色。
* 如果发现一个邻居已经被涂过色，且**颜色和当前点相同**，说明发生了冲突，这就**不是二分图**。

---

## 13. 匈牙利算法

### 作用
解决**二分图的最大匹配问题**（例如：媒婆给单身男女牵线，如何让成功牵手的情侣对数最多？）。
### 核心思想
“先到先得，择优谦让”。如果男生 A 想选女生 B，但 B 已经被男生 C 选走了，算法会尝试去问 C：“你能不能换个备胎？把 B 让给 A。”如果 C 能找到新备胎，A 就成功配对，否则 A 只能再找别人。

---

搜索与图论模块讲义

本模块包含 DFS、BFS、树与图的深度优先遍历、树与图的广度优先遍历、拓扑排序、Dijkstra、Bellman-Ford、SPFA、Floyd、Prim、Kruskal、染色法判定二分图、匈牙利算法 共 13 个核心图论与搜索算法。

1. DFS (深度优先搜索 - Depth First Search)

核心思想与性格

性格：不撞南墙不回头。
做法：一条路走到黑。先选一条路一直往前走，走不通了（死胡同）就退回上一步（这叫回溯），换一条路再试，直到把所有的可能性全部搜完。通常使用递归实现。

经典应用：全排列问题

用 DFS 生成 $1 \sim n$ 的全排列：

int path[N], st[N]; // path存当前路径，st记录哪个数字被用过了
void dfs(int u) {
    if (u > n) {
        for (int i = 1; i <= n; i++) cout << path[i] << " ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!st[i]) {
            st[i] = true; path[u] = i;
            dfs(u + 1);
            st[i] = false; // 回溯，恢复现场
        }
    }
}

2. BFS (广度优先搜索 - Breadth First Search)

核心思想与性格

性格：稳扎稳打，层层推进。
做法：像水波纹一样向四周一圈一圈扩散。先看离起点距离为 1 的所有点，再看距离为 2 的所有点……
特点：通常使用队列 (Queue) 实现。在边权全部相等（或无权图）的情况下，BFS 搜索到目标时，走过的步数一定是最短路。

3. 树与图的深度优先遍历 & 4. 树与图的广度优先遍历

图的存储：邻接表

在计算机里，我们用邻接表来存图。每一个节点都有一个链表，记录它能直接走到哪些邻居。

// h[N] 存每个点链表的头节点，e[] 存邻居是谁，ne[] 存下一条边
int h[N], e[M], ne[M], idx;

void add(int a, int b) { // 添加一条从 a 到 b 的有向边
    e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}

树的 DFS：递归遍历每个节点的子树，常用于求树的深度、子树节点个数。
树的 BFS：利用队列进行层序遍历，常用于求树的宽度或按层处理信息。

5. 拓扑排序 (Topological Sort)

核心思想

场景：学校选课。想学《高等数学》必须先学《初等数学》。
拓扑排序：把一张有向无环图（DAG）的所有节点排成一个线性序列，使得对图中的每一条有向边 $(u, v)$，$u$ 都排在 $v$ 的前面。
入度：有几条边指向这个点。

算法步骤

把所有入度为 0 的点（没有前置要求）放入队列。
队头元素出队，把它指向的邻居的入度减 1。
如果邻居的入度减到了 0，立刻把这个邻居也丢进队列。
重复直到队列为空。如果最后所有点都被遍历到了，说明存在拓扑排序（图无环）。

6. Dijkstra 算法

作用与限制

作用：求单源最短路径（从一个起点到其他所有点的最短距离）。
核心限制：图里面绝对不能有负权边（否则贪心会失效）。
时间复杂度：朴素版 $O(n^2)$，堆优化版 $O(m \log n)$。

贪心策略

每次从未确定最短路的点中，挑一个离起点最近的点，把它标记为“已确定”，然后用它去更新它所有邻居的距离（这叫松弛操作）。

// 堆优化 Dijkstra 核心逻辑
priority_queue<PII, vector<PII>, greater<PII>> heap;
dist[1] = 0;
heap.push({0, 1}); // {距离, 点编号}

while (heap.size()) {
    auto t = heap.top(); heap.pop();
    int ver = t.second, distance = t.first;
    if (st[ver]) continue;
    st[ver] = true;

    for (int i = h[ver]; i != -1; i = ne[i]) {
        int j = e[i];
        if (dist[j] > distance + w[i]) {
            dist[j] = distance + w[i];
            heap.push({dist[j], j});
        }
    }
}

7. Bellman-Ford 算法

作用与特点

作用：求单源最短路，允许图中有负权边。
负权回路：如果图中存在一个环，且环上的边权总和为负数，那么绕这个环转一圈距离就会变小无限次，最短路就不存在。Bellman-Ford 可以检测负权回路。
核心做法：对所有的边进行 $n-1$ 次松弛操作。如果第 $n$ 次循环还能松弛，说明存在负环。

8. SPFA 算法 (Shortest Path Faster Algorithm)

核心思想

本质：它是 Bellman-Ford 算法的队列优化版。
优化逻辑：Bellman-Ford 每次盲目检查所有的边太慢了。SPFA 发现：只有当一个点的最短距离变小了，它才有资格去更新它的邻居。所以用一个队列把“距离变小了的点”存起来。在大多数没有负环的图里，SPFA 运行速度极快。

9. Floyd 算法

作用与精妙代码

作用：求多源汇最短路径（图里任意两个点之间的最短距离），允许负权边，但不能有负环。
核心思想（动态规划）：三层循环。外层枚举中转站 $k$（$1 \to n$），内层枚举起点 $i$ 和终点 $j$。如果通过 $k$ 中转能让路程变短，就更新它： $$d[i][j] = \min(d[i][j], d[i][k] + d[k][j])$$
代码极短： cpp for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

10. Prim 算法

作用

求最小生成树 (MST)。给定一张带权连通图，用最少的边（刚好 $n-1$ 条）把所有点连起来，且所有边的总权值最小。

做法

Prim 算法和 Dijkstra 极其相似： * Dijkstra 是求点到起点的距离，Prim 是求点到当前生成树的距离。 * 每次挑一个离生成树最近的点加入树中，并更新其他点到生成树的距离。

11. Kruskal 算法

作用与直观步骤

另一种求最小生成树的方法，代码简单且极其直观。 1. 排序：把图中的所有边按照权值从小到大排序。 2. 挑选：从小到大扫描每条边 $(u, v)$： * 用并查集判断 $u$ 和 $v$ 是否已经连通。 * 如果不连通，说明没有成环，把这条边选入生成树，并将 $u$ 和 $v$ 合并。 * 直到选够 $n-1$ 条边为止。

12. 染色法判定二分图

什么是二分图？

如果能把图中的所有点分成两个集合，使得图里所有的边都横跨在两个集合之间（同一个集合内部的点之间没有连线），这张图就是二分图。

做法（DFS / BFS）

遍历整张图，用两种颜色（比如 1 和 2）轮流涂色： * 如果搜索到一个未涂色的邻居，把它涂成与当前点不同的颜色。 * 如果发现一个邻居已经被涂过色，且颜色和当前点相同，说明发生了冲突，这就不是二分图。

13. 匈牙利算法

作用

解决二分图的最大匹配问题（例如：媒婆给单身男女牵线，如何让成功牵手的情侣对数最多？）。

核心思想

“先到先得，择优谦让”。如果男生 A 想选女生 B，但 B 已经被男生 C 选走了，算法会尝试去问 C：“你能不能换个备胎？把 B 让给 A。”如果 C 能找到新备胎，A 就成功配对，否则 A 只能再找别人。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com