算法设计：稳定匹配与图

稳定匹配是算法设计的第一个例子：给出一个过程，证明它终止、给出正确的解，再估计它的代价。图则是此后几乎所有问题的语言，图上的算法大多从遍历开始，而遍历的代价是 $O(m+n)$，与读入图的代价相同。

1. 引入：稳定匹配

有 $n$ 位男士 $M$ 与 $n$ 位女士 $W$，每人对异性有一个严格的偏好排序。匹配 $S\subseteq M\times W$ 中每人至多出现一次；每人恰好出现一次时称为完美匹配。对完美匹配 $S$，若 $(m,w)\notin S$，而 $m$ 比起自己的配偶更喜欢 $w$，$w$ 比起自己的配偶也更喜欢 $m$，则称 $(m,w)$ 为不稳定对。没有不稳定对的完美匹配称为稳定匹配。

给定 $2n$ 个人的偏好表，求一个稳定匹配（若存在）。

完美匹配共 $n!$ 个，逐一检查是否存在不稳定对，复杂度为 $O(n!\,n^2)$；输入是 $2n$ 张长为 $n$ 的偏好表，读入即需 $\Omega(n^2)$。

稳定匹配是否总存在并不显然。若不区分两方（室友问题：$2n$ 个人两两配对），它就可能不存在：

Gale 与 Shapley（1962）给出了一个“提议—拒绝”的过程：未配对的男士按偏好从高到低依次向女士提议；女士只保留目前收到的最好的提议，拒绝其余的。

\begin{algorithm}
\caption{Gale-Shapley：稳定匹配}
\begin{algorithmic}
\PROCEDURE{GaleShapley}{男士与女士的偏好表}
  \STATE $S \gets \emptyset$
  \WHILE{存在未配对、且未向所有女士提议过的男士 $m$}
    \STATE $w \gets m$ 的偏好表中他尚未提议过的排名最高的女士
    \IF{$w$ 未配对}
      \STATE $S \gets S \cup \{(m, w)\}$
    \ELIF{$w$ 比起当前配偶 $m'$ 更喜欢 $m$}
      \STATE $S \gets S - \{(m', w)\} \cup \{(m, w)\}$ \COMMENT{$m'$ 重新成为未配对}
    \ELSE
      \STATE $w$ 拒绝 $m$
    \ENDIF
  \ENDWHILE
  \RETURN $S$
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

过程中有两个单调的量：男士提议的对象越来越差；女士一旦配对就不会再落单，配偶只会越来越好。分析就建立在这两点之上。

对任意偏好表，Gale–Shapley 算法都在至多 $n^2$ 轮后返回一个稳定匹配。特别地，稳定匹配总是存在。

2. 实现：与输入同阶

$n^2$ 轮只是轮数的上界。要使总时间为 $O(n^2)$，每一轮必须在 $O(1)$ 内完成，即以下四个操作都是常数时间：

找一位未配对的男士：用链表（或栈）维护未配对的男士，取出与放回都是 $O(1)$；

找他尚未提议过的最好的女士：数组 $\mathrm{Next}[m]$ 记录他下一个要提议的位置，提议后无论结果都加一；

查女士的当前配偶：数组 $\mathrm{Current}[w]$，未配对时为空；

比较女士对两位男士的偏好：偏好表 $\mathrm{WomanPref}[w,i]$ 给出的是第 $i$ 名是谁，比较需要 $O(n)$；预先计算其逆 $\mathrm{Ranking}[w,m]$（$m$ 在 $w$ 心中的名次），只需 $O(n^2)$ 的预处理，此后比较为 $O(1)$。

前三者只是选对数据结构，第四个则需要把输入转换成更适合算法的形式。合计 $O(n^2)$，与读入输入的下界同阶。

\begin{algorithm}
\caption{Gale-Shapley 的 $O(n^2)$ 实现}
\begin{algorithmic}
\PROCEDURE{GaleShapleyArrays}{$\mathrm{ManPref}, \mathrm{WomanPref}$}
  \FORALL{$w$ 与 $i \gets 1, \dots, n$}
    \STATE $\mathrm{Ranking}[w, \mathrm{WomanPref}[w, i]] \gets i$ \COMMENT{预处理 $O(n^2)$}
  \ENDFOR
  \STATE 对一切 $m$：$\mathrm{Next}[m] \gets 1$；对一切 $w$：$\mathrm{Current}[w] \gets \mathrm{null}$
  \STATE $F \gets$ 全部男士组成的栈
  \WHILE{$F$ 非空}
    \STATE $m \gets$ \CALL{Pop}{$F$}，$w \gets \mathrm{ManPref}[m, \mathrm{Next}[m]]$，$\mathrm{Next}[m] \gets \mathrm{Next}[m] + 1$
    \STATE $m' \gets \mathrm{Current}[w]$
    \IF{$m' = \mathrm{null}$}
      \STATE $\mathrm{Current}[w] \gets m$
    \ELIF{$\mathrm{Ranking}[w, m] < \mathrm{Ranking}[w, m']$}
      \STATE $\mathrm{Current}[w] \gets m$，\CALL{Push}{$F, m'$}
    \ELSE
      \STATE \CALL{Push}{$F, m$} \COMMENT{被拒绝，下一轮继续向下一位提议}
    \ENDIF
  \ENDWHILE
  \RETURN $\{(\mathrm{Current}[w], w) : w \in W\}$
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

由“完美”引理，栈中的男士总还有没提议过的女士，$\mathrm{Next}[m]$ 不会越界。

3. 理解解：男方最优

同一组偏好可以有多个稳定匹配，例如

中 $\{X\text{–}A,\ Y\text{–}B,\ Z\text{–}C\}$ 与 $\{X\text{–}B,\ Y\text{–}A,\ Z\text{–}C\}$ 都是稳定的：前者男士都得到首选，后者女士 $A,B$ 都得到首选。算法中“选一位未配对的男士”是任意的，不同的执行顺序会得到不同的结果吗？

若存在某个稳定匹配使 $m$ 与 $w$ 配对，则称 $w$ 是 $m$ 的可行配偶。记 $\mathrm{best}(m)$ 为 $m$ 的可行配偶中他最喜欢的一位，$\mathrm{worst}(w)$ 为 $w$ 的可行配偶中她最不喜欢的一位。

由此，“每位男士都得到最好的可行配偶”这一看似过分的要求，竟然给出一个匹配，而且是稳定的。代价由另一方承担：

提议的一方占优。由女士提议得到的就是女方最优、男方最劣的稳定匹配，上例中两个稳定匹配正是如此。

4. 五个代表性问题

稳定匹配之后，几个形式相近的问题刻画了算法设计的不同难度：

后三个是图上的问题，而前三个都是（带权）独立集的特例：以区间为节点、相交的区间之间连边（区间图），区间调度就是区间图上的独立集；以二分图的边为节点、有公共端点的边之间连边，匹配就是这个图上的独立集。同一个问题，在一般图上是 NP 完全的，在特殊结构的图上却有高效算法。区间调度的贪心见算法设计：贪心。

5. 图：定义与表示

无向图 $G=(V,E)$ 由节点集 $V$ 与边集 $E$ 组成，每条边连接一对节点，记 $n=|V|$，$m=|E|$。有向图中边 $(u,v)$ 有方向，从尾 $u$ 指向头 $v$。路径是节点序列 $v_1,\dots,v_k$，相邻两点有边相连；节点互不相同时称为简单路径。任意两点间都有路径的无向图称为连通的。$v_1=v_k$、$k>2$ 且前 $k-1$ 个节点互不相同的路径称为圈。

在算法中，同一个图可以有不同的表示，各有所长：

邻接矩阵 $A_{uv}=[(u,v)\in E]$ 适合稠密图与 $O(1)$ 的查询；图通常是稀疏的（$m\ll n^2$），此时邻接表更好。由握手引理，遍历全部邻接表的代价是 $\Theta(m+n)$，这正是下文“线性时间”的含义。

前向星是邻接表的数组形式：将边按尾节点排序存入数组，再用 $\mathrm{point}[u]$ 记录从 $u$ 出发的第一条边的编号，$u$ 的出边即编号 $\mathrm{point}[u],\dots,\mathrm{point}[u+1]-1$ 的边。例如有向图 $1\to2,\ 1\to3,\ 2\to4,\ 3\to2,\ 4\to3,\ 4\to5,\ 5\to3,\ 5\to4$：

（$\mathrm{point}[6]=9$ 是哨兵。）同理可按头节点排序得到反向星，用于遍历入边。

关联矩阵 $B\in\{-1,0,1\}^{n\times m}$ 的每列对应一条边：边 $e=(u,v)$ 在第 $u$ 行为 $1$，第 $v$ 行为 $-1$，其余为 $0$。它不适合遍历，但把图论性质变成了线性代数性质：

无圈的连通图称为树。选定一个根 $r$ 并将边背离 $r$ 定向，就得到有根树，其中有父节点、子节点、祖先与后代的概念。

6. 连通性：BFS 与 DFS

给定图 $G$ 与节点 $s,t$，判断是否存在 $s$ 到 $t$ 的路径；若存在，求最短路径的边数。

枚举所有路径是指数级的；算法可能需要看过每条边才能断定不连通，下界为 $\Omega(m+n)$。

广度优先搜索（BFS）则考虑从 $s$ 出发逐层向外扩展：$L_0=\{s\}$；$L_{j+1}$ 由不在 $L_0,\dots,L_j$ 中、但与 $L_j$ 中某点相邻的节点组成。

每个 $v\in L_{j+1}$ 记下发现它的 $L_j$ 中的节点作为父节点，就得到以 $s$ 为根的 BFS 树。

用队列实现时，每个节点至多入队一次，出队时扫描其邻接表，代价为 $O(\deg u)$；由握手引理，总代价为 $O(m+n)$。

\begin{algorithm}
\caption{BFS：分层与最短跳数}
\begin{algorithmic}
\PROCEDURE{BFS}{$G, s$}
  \STATE 对一切 $v$：$\mathrm{dist}(v) \gets \infty$，$\mathrm{parent}(v) \gets \mathrm{null}$
  \STATE $\mathrm{dist}(s) \gets 0$，$Q \gets$ 只含 $s$ 的队列
  \WHILE{$Q$ 非空}
    \STATE $u \gets$ \CALL{Dequeue}{$Q$}
    \FORALL{$u$ 的邻居 $v$}
      \IF{$\mathrm{dist}(v) = \infty$}
        \STATE $\mathrm{dist}(v) \gets \mathrm{dist}(u) + 1$，$\mathrm{parent}(v) \gets u$ \COMMENT{$v \in L_{\mathrm{dist}(v)}$}
        \STATE \CALL{Enqueue}{$Q, v$}
      \ENDIF
    \ENDFOR
  \ENDWHILE
  \RETURN $\mathrm{dist}, \mathrm{parent}$
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

深度优先搜索（DFS）则考虑沿一条路一直走下去，走不通再回溯，就像在迷宫中一手扶墙。以 DFS 调用关系为父子关系，得到 DFS 树。

用递归（或显式的栈）实现，同样是 $O(m+n)$。

\begin{algorithm}
\caption{DFS：深度优先搜索}
\begin{algorithmic}
\PROCEDURE{DFS}{$u$}
  \STATE 将 $u$ 标记为已访问
  \FORALL{$u$ 的邻居 $v$}
    \IF{$v$ 未被访问}
      \STATE $\mathrm{parent}(v) \gets u$
      \STATE \CALL{DFS}{$v$}
    \ENDIF
  \ENDFOR
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

两者访问的节点集合相同，都是 $s$ 所在的连通块，只是树的形状不同：BFS 树又矮又宽，非树边只连接相邻层；DFS 树又高又窄，非树边只连接祖先与后代。两点的连通块要么相同、要么不相交，反复从未访问的节点出发搜索，即可在 $O(m+n)$ 内求出全部连通块。边带非负长度时，按距离而非层数扩展，就得到 Dijkstra 算法，见算法设计：贪心。

7. 二分图判定

若能把无向图的节点染成红、蓝两色，使每条边的两端颜色不同，则称其为二分图。

稳定匹配中男士与女士、调度中机器与任务都构成二分图。许多图问题在二分图上更简单（匹配），或从难解变为可解（独立集）。

给定无向图 $G$，判断它是否为二分图。

奇圈是一个显然的障碍：沿圈交替染色，绕一圈回到起点时颜色必须改变奇数次，矛盾。BFS 表明它也是唯一的障碍：

无向图是二分图，当且仅当它不含奇圈。

于是只需在每个连通块上 BFS，按层的奇偶染色，再检查每条边，共 $O(m+n)$。

\begin{algorithm}
\caption{Is-Bipartite：二分图判定}
\begin{algorithmic}
\PROCEDURE{IsBipartite}{$G$}
  \FORALL{$v \in V$}
    \IF{$v$ 未被访问}
      \STATE $\mathrm{dist}(v) \gets 0$，从 $v$ 出发 BFS，求出该连通块内各点的 $\mathrm{dist}$ \COMMENT{不重置其它连通块}
    \ENDIF
  \ENDFOR
  \STATE $\mathrm{color}(v) \gets \mathrm{dist}(v) \bmod 2$ \COMMENT{按层的奇偶染色}
  \FORALL{边 $(x, y) \in E$}
    \IF{$\mathrm{color}(x) = \mathrm{color}(y)$}
      \RETURN \FALSE \COMMENT{同层边，存在奇圈}
    \ENDIF
  \ENDFOR
  \RETURN \TRUE
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

8. 有向图：强连通

在有向图中，BFS 与 DFS 沿出边进行即可，求出的是从 $s$ 可达的节点。反过来，求“哪些节点能到达 $s$”，只需在反图 $G^{\mathrm{rev}}$（每条边反向）上搜索，反图可在 $O(m+n)$ 内建出。

若 $u$ 到 $v$、$v$ 到 $u$ 都有路径，则称 $u,v$ 互相可达。任意两点都互相可达的有向图称为强连通的。

互相可达是等价关系（传递性：把 $u\to v$ 与 $v\to w$ 的路径接起来即可），其等价类称为强连通分量。两点的强连通分量要么相同，要么不相交。

Tarjan（1972）进一步给出了在 $O(m+n)$ 内求出全部强连通分量的算法，见文末补充。

9. 有向无环图与拓扑序

不含有向圈的有向图称为有向无环图（DAG）。有向图的拓扑序是节点的一个排列 $v_1,\dots,v_n$，使每条边 $(v_i,v_j)$ 都满足 $i < j$。

DAG 刻画了先后约束：边 $(v_i,v_j)$ 表示任务 $v_i$ 必须先于 $v_j$，如课程的先修关系、模块的编译顺序、流水线中作业的输入输出依赖。拓扑序就是一个满足所有约束的执行顺序。

这个证明本身就是算法：反复取出入度为零的节点并删去。朴素地每次重新寻找需要 $O(n^2)$；维护每个节点剩余的入度 $\mathrm{count}(w)$ 与当前入度为零的节点集合 $Z$，删去 $v$ 时只需对每条出边 $(v,w)$ 将 $\mathrm{count}(w)$ 减一，每条边 $O(1)$，共 $O(m+n)$。若 $Z$ 在输出全部节点之前就空了，剩下的子图没有入度为零的节点，$G$ 含有向圈。

\begin{algorithm}
\caption{Topological-Sort：拓扑排序}
\begin{algorithmic}
\PROCEDURE{TopologicalSort}{$G$}
  \STATE 对一切 $w$：$\mathrm{count}(w) \gets w$ 的入度 \COMMENT{扫描一遍，$O(m + n)$}
  \STATE $Z \gets \{w : \mathrm{count}(w) = 0\}$，$L \gets$ 空表
  \WHILE{$Z$ 非空}
    \STATE 从 $Z$ 中取出某个 $v$，追加到 $L$ 末尾
    \FORALL{边 $(v, w)$}
      \STATE $\mathrm{count}(w) \gets \mathrm{count}(w) - 1$
      \IF{$\mathrm{count}(w) = 0$}
        \STATE $Z \gets Z \cup \{w\}$
      \ENDIF
    \ENDFOR
  \ENDWHILE
  \IF{$|L| < n$}
    \RETURN 含有向圈
  \ENDIF
  \RETURN $L$
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

10. 几个小例子

\begin{algorithm}
\caption{Robots：构型空间中的搜索}
\begin{algorithmic}
\PROCEDURE{Robots}{$G, a, b, c, d, r$}
  \FORALL{$u \in V$}
    \STATE \CALL{BFS}{$G, u$}，得到 $d_G(u, \cdot)$ \COMMENT{共 $O(n(m + n))$}
  \ENDFOR
  \STATE $V' \gets \{(u, v) : d_G(u, v) > r\}$
  \STATE $E' \gets \{((u, v), (u', v)) : (u, u') \in E\} \cup \{((u, v), (u, v')) : (v, v') \in E\}$，限制在 $V'$ 上
  \STATE 在 $H' = (V', E')$ 中从 $(a, b)$ 出发 \CALL{BFS}{} \COMMENT{$O(mn + n^2)$}
  \RETURN $(c, d)$ 是否被访问到
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

11. 小结

稳定匹配的分析示范了算法分析的全部要素：用单调量证明终止，用不变量证明正确，再为每一步选择数据结构使总代价与输入同阶。图上的基本问题则几乎都归结为一次遍历：选对表示（邻接表）使遍历为 $O(m+n)$，再从遍历留下的结构（层、树、入度）中读出答案。

12. 补充：强连通分量与缩点

强连通一节只判定了整个图是否强连通。一般的有向图可以分解为强连通分量，而分量之间的结构恰好是上一节的 DAG。

于是任何有向图都是“强连通分量组成的 DAG”。求强连通分量的关键是找到缩点 DAG 的一个汇（没有出边的分量）：从汇中任一点出发搜索，恰好访问这个分量，不会漏到别处。DFS 的完成时间可以找到它。对整个图反复从未访问的点发起 DFS，记 $\mathrm{post}(u)$ 为 DFS$(u)$ 返回的时刻。

于是完成时间最大的点位于缩点 DAG 的一个源（没有入边的分量）中；在反图中源变成汇。由此得到 Kosaraju–Sharir 算法：

\begin{algorithm}
\caption{Kosaraju-Sharir：强连通分量}
\begin{algorithmic}
\PROCEDURE{SCC}{$G$}
  \STATE 在 $G$ 上反复从未访问的节点调用 DFS，按完成时间降序记录节点，得到 $P$
  \STATE 构造反图 $G^{\mathrm{rev}}$，将所有节点重新标为未访问
  \FORALL{$u \in P$，按降序}
    \IF{$u$ 未被访问}
      \STATE 在 $G^{\mathrm{rev}}$ 上调用 \CALL{DFS}{$u$}，本次访问到的节点构成一个强连通分量
    \ENDIF
  \ENDFOR
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

特别地，若 $G$ 本身是 DAG，每个分量只有一个点，完成时间引理说的是：每条边 $(u,v)$ 都满足 $\mathrm{post}(u) > \mathrm{post}(v)$。于是按完成时间降序排列节点就是一个拓扑序，这是拓扑排序的另一种 $O(m+n)$ 实现。Tarjan 的算法只用一次 DFS，为每个节点维护它经由后代与一条非树边能回到的、仍在栈中的最早节点（low-link），在 DFS 返回时就地识别出每个分量的根，复杂度同样为 $O(m+n)$。