离散数学&数据结构-图论常匹配问题与算法概括

基本图论算法

一、最小生成树（Minimum Spanning Tree，MST）

• 关键词：连通、造价最小、覆盖所有点、不关注路径、不成环

• 典型题干：

  设计一个通信网络，使所有城市能互相通信且造价最小。

• 常用算法：

  • Kruskal：按边权升序排序，逐条选入，不成环为准。
  • Prim：从任意点出发，逐步扩展最短连边进集合。

• 适用问题类型：

  • 网络建设、城市连接、铺设电缆、布线等

---

二、最短路径（Single/All Pairs Shortest Path）

• 关键词：从某点到某点路径最短、有向/无向图、有权图
• 典型题干

  求 A 城市到其他城市的最短路径。

• 常用算法：
  • Dijkstra：正权图单源最短路径（常用于地图/网路延迟）
  • SPFA：负边权也能跑，适用于稀疏图
  • Floyd：所有点对最短路径，三重循环（适用于稠密图）
• 适用问题类型：
  • 地图导航、路线规划、网络延迟最小化

---

三、旅行商问题（Traveling Salesman Problem，TSP）

• 关键词：访问所有点、只访问一次、形成闭环、最短路径
• 典型题干：

  某人需访问所有城市一次并返回起点，求最短路线。

• 常用算法：
  • 暴力搜索 / 状压 DP / 分支限界 / 启发式搜索（如遗传算法）
• 适用问题类型
  • 快递路线、外卖送货、城市巡回问题

---

四、中国邮路问题（Euler 回路）

• 关键词：走遍所有边一次、不重复、回到起点或不回起点
• 典型题干：

  邮递员需要经过每条街道一次，如何规划路线？

• 常用算法：
  • Hierholzer 算法：找欧拉回路或路径
  • 判断条件：
    • 欧拉回路：所有点度数为偶数
    • 欧拉路径：最多两个点为奇数度
• 适用问题类型：
  • 邮递、清扫机器人、巡检线路问题

---

五、拓扑排序问题（DAG 上的排序）

• 关键词：有向无环图、先修课程、依赖关系、顺序安排
• 典型题干：

  给定课程依赖关系，安排上课顺序。

• 常用算法：
  • 拓扑排序（BFS/Kahn）
  • DFS 建序列（逆后序）

---

一眼看图识题技巧

问题关键词	属于哪一类	应用算法
连通、造价最小	最小生成树（MST）	Prim / Kruskal
起点到各点最短	最短路径	Dijkstra / SPFA
所有点走一圈	旅行商问题（TSP）	状压 DP / 搜索
所有边走一遍	中国邮路（Euler 回路）	Hierholzer
有依赖顺序安排	拓扑排序（DAG）	Kahn / DFS

---

图论算法衍生

网络流

EK算法最大流

最大流问题就是：

想象你是个调水的管道工： 有个源点（source）：水从这儿开始流。 有个汇点（sink）：水最终要流到这。 图里的每条边是水管，有个最大能流多少水的限制（容量）。 你要解决的核心问题就是 “从源点最多能往汇点送多少水？”

• 问题：在给定容量限制下，从源点到汇点的最大可能流量。
• 经典算法：Ford-Fulkerson（增广路径）、Edmonds-Karp（BFS）、Dinic（分层图 + DFS）。

EK算法最大流是：

用广度优先去找：从源点到汇点还有没有“能通的水路”。 找到就“倒水”：找出这条路上最细的那根管子（瓶颈），推这么多流量。 更新管道：把用掉的流量减去，剩下的再来。 直到你怎么找都找不到新路了：那就是最大流了。

Edmonds-Karp 是一种 基于广度优先搜索（BFS） 的最大流算法，属于 Ford-Fulkerson 方法的实现之一。 注意：离散数学考试给予简化版本，不维护反向边。

它的核心思想是：
每次用 BFS 在残量网络中找一条从源点 S 到汇点 T 的最短增广路径，然后将该路径上的可增广流量加入到总流中，并更新残量网络。

核心结构

• 残量网络：对于每条边 (u,v)，我们维护： 正向边容量 c(u,v) 当前流量 f(u,v) 残余容量 r(u,v) = c(u,v) - f(u,v) 并添加反向边 (v,u)，其残余容量为 f(u,v)，表示可以“退回”流量。

假设你有如下图的网络：

S --(10)--> A --(5)--> T
 \                      /
  \----(15)------------/

你用 BFS 找到 S->A->T，可增广流为 5，再找 S->T，可增广流为 15。
总流量 5 + 15 = 20，路径更新后不能再增广，算法结束。

最小割

• 割：将所有节点分为两个集合 S集合 和 T集合，使得源点 S 在 S集合，汇点 T 在 T集合。

• 最小割：在所有可能的割中，跨越两个集合的边的容量之和最小的割。

• 问题：将图中点集分为两部分，使得源点在一侧，汇点在另一侧，割掉的边容量总和最小。

• 定理：最大流 = 最小割。 在一个有向图中，从源点 S 到汇点 T 的最大流的大小，等于从 S 到 T 的最小割的容量。

最大流 = 能从水库 S 送到城市 T 的最多水量 最小割 = 一刀下去能阻断的最小总水流（把某些管道切掉） 换句话说： 最大你能送的 = 最少别人能拦的

S --(3)--> A --(2)--> T
 \                  /
  \----(4)--------/

最大流是 5（S→A→T 走 2，S→T 走 3） 最小割是割断 S→T 和 A→T（容量是 3+2=5） 他们相等，定理成立。

---

术语	定义（通俗解释）
网络流图	一个带有容量限制的有向图，每条边表示“能容纳多少流量”。
源点（S）	流量的起点，像是“水库”或“工厂”。
汇点（T）	流量的终点，像是“城市”或“消费者”。
流量（Flow）	实际通过边的流量，不能超过边的容量。
容量（Capacity）	边所能承受的最大流量，相当于“管道粗细”。
残量网络	当前流量状态下，图中还可以继续“走”的路径与容量。
增广路	在残量网络中，从源点到汇点还可以“加流”的路径。
最大流	从源点到汇点能“加”上的最大总流量。
割（Cut）	把图的点分成两个集合，源点在一边，汇点在另一边。
割的容量	从源点集合通向汇点集合的边的容量总和。
最小割	所有可能割中，容量最小的一个，表示“最小阻断能力”。
最大流最小割定理	最大能通过的流量 = 最小能拦下的割。
EK算法（Edmonds-Karp）	使用 BFS 查找增广路，逐步累加流量，直到没有增广路。时间复杂度 O(VE²)。
Dinic算法	更快的最大流算法，基于分层图+DFS增广。时间复杂度 O(V²E)（稀疏图较优）。