Posted in未分类
Tarjan 图分解器实战指南:两个算法,一张错的图
两个独立算法读同一份错误输入,会彼此一致,也会一致地违背你真正想画的那张图。我把 Tarjan 强连通分量 / 桥 / 关节点分解与拓扑排序器 的源码逐段看了一遍,把它报出的每个数重新推了一遍。在工具自带的 7 节点示例上,两个算法完全吻合;在你敲进去的图并不是你画的那张图时,它们同样完全吻合。这到底算谁的 bug? 交叉验证是真的,但它验的不是你的输入 工具对同一份边列表跑好几遍。它解析图,跑 Tarjan 强连通分量算法,再在反向图上跑…