拓扑排序（Topological Sort）这个算法名字听起来像数学系黑话，但它干的事特别接地气：给一堆有先后顺序的任务排个队。比如超人穿衣服——内裤外穿是经典造型，但如果你想让他"正常"一点，得先搞清楚哪件必须先穿。
卡恩（Kahn）在1962年提出的这个方法，核心就一句话：先找那些不需要前置条件的任务，干掉它，再看有没有新任务解锁，循环往复。这过程像极了游戏里的任务链：完成A才能接B，B做完C才亮起来。
超人的7件装备，依赖关系有多乱
原文给超人列了全套行头：紧身衣上衣（Skintight Top）、红披风（Red Cape）、红内裤（Red Briefs）、紧身衣裤子（Skintight Pants）、胸前盾牌标志（Shield Emblem）、红靴子（Red Boots）。
依赖关系写成这样：
('Skintight Top', 'Red Cape') —— 先穿上衣，才能披披风
('Red Briefs', 'Skintight Pants') —— 先穿内裤，才能套裤子
('Skintight Top', 'Shield Emblem') —— 先穿上衣，才能别标志
('Red Boots', 'Skintight Pants') —— 先穿靴子，才能穿裤子
注意最后一条。靴子必须在裤子之前？这设计有点反直觉，但原文就这么定的——可能是靴子要塞进裤腿里。总之规则就是规则，算法不管合不合理，只管有没有环。
第一步扫描所有依赖，找出"入度为零"的节点：Skintight Top、Red Briefs、Red Boots。这三件随便穿，没人管它们。
卡恩算法的两步走：删节点、降入度
算法流程像剥洋葱。把入度为零的节点扔进结果队列，然后从图里删掉它，同时把它指向的那些节点的入度各减1。
第一轮：选Skintight Top。删掉它之后，Red Cape和Shield Emblem的入度从1变成0，解锁。
第二轮：Red Briefs。删掉后，Skintight Pants的入度从2变成1（还在等Red Boots）。
第三轮：Red Boots。删掉后，Skintight Pants的入度从1变成0，终于解锁。
第四轮：Red Cape、Shield Emblem、Skintight Pants，三者入度都是0，顺序任意。
整个流程用队列就能实现，时间复杂度O(V+E)，V是顶点数，E是边数。对于超人的7件衣服，这算法跑完连一毫秒都不到。
代码实现：26行Python说清楚
原文给的实现很干净。核心数据结构：邻接表存图，数组存入度，队列存待处理节点。
初始化阶段遍历所有边，统计每个节点的入度。然后把入度为0的节点全部入队——这是卡恩算法和深度优先搜索（DFS）版拓扑排序的关键区别：DFS是递归到底再回溯，卡恩是广度优先，一层层剥。
队列处理循环里，每弹出一个节点，就遍历它的所有邻居，入度减1。减到0立刻入队，保证队列里始终只有"现在就能做"的任务。
最后检查结果长度。如果小于总节点数，说明图里有环——比如规定"穿A必须先穿B，穿B必须先穿A"，这衣服永远穿不上。卡恩算法能检测这种死锁，这是它比单纯排序多出来的价值。
从超人到编译器：同一个算法，两种人生
穿衣顺序是 toy example，但依赖解析是刚需。编译器处理源文件时，A.cpp 依赖 B.h，B.h 又依赖 C.h，链接器必须按正确顺序生成目标文件。卡恩算法就是 make 工具背后的理论支撑。
数据库迁移脚本同理。表A的外键指向表B，表B的外键指向表C，执行顺序错了直接报错。运维工具用拓扑排序生成迁移计划，和超人穿衣服是同一个数学问题。
甚至你的npm install也在用。包X依赖包Y的特定版本，Y又依赖Z，解析器要算出满足所有约束的安装顺序。环形依赖？报错，和人类发现超人内裤外穿一样无法容忍。
卡恩算法的优雅在于，它把"先后顺序"这个模糊概念，转化成了可计算的图论问题。入度、邻接表、队列——这些结构没有一句提到"衣服"或"编译"，却能统一解决两类看似无关的需求。
超人的7件衣服排完序，有6种合法方案（最后三件无依赖，3! = 6）。但不管选哪种，红披风永远不会在紧身衣之前飘起来——算法的保证，比超人的披风还稳。
如果让你给钢铁侠的42代战甲写穿衣算法，Mark 1到Mark 42的依赖关系会比超人复杂几个数量级——你觉得卡恩算法还够用吗，还是得请出更重的动态规划？
热门跟贴