《算法的乐趣》第二十节

本节先给出穷举所有完美匹配的递归算法：按男孩顺序逐个从其偏爱列表中挑选尚未有舞伴的女孩，配对后递归处理下一个男孩，末位配对完成即得到一个完美匹配，每级搜索后需回溯重置关系。

本节先给出穷举所有完美匹配的递归算法：按男孩顺序逐个从其偏爱列表中挑选尚未有舞伴的女孩，配对后递归处理下一个男孩，末位配对完成即得到一个完美匹配，每级搜索后需回溯重置关系。随后给出稳定匹配的判断流程：若某男孩的当前舞伴不是其偏爱列表首位，且他更偏爱的女孩也更偏爱他胜过其现任，则该匹配不稳定；逐男检查，全部通过即为稳定匹配。实例中穷举得到两个稳定匹配，而Gale-Shapley算法只得到其中一个；并提及稳定匹配数总是2的整数幂、女孩偏爱列表全同时仅有一种稳定匹配。之后引入二部图：顶点集分为两部分、边两端分属不同集合；边互不共点的子图是匹配，边数最多的为最大匹配，无未覆盖点的最大匹配即完美匹配。求最大匹配可用匈牙利算法：反复寻找增广路径——奇数条边、左右交替、点不重复、仅两端未覆盖、奇数边不在匹配中而偶数边在其中——对其取反可使匹配数加一，直到找不到增广路径为止，此时即最大匹配。文中还给出了该算法的数据结构与从Xi出发递归搜索增广路径的实现要点。