具有循环的图形的“拓扑”排序

文章的完整标题应该是“可持续的”拓扑“按时间顺序以O(|V| + |e| log |e|)和O(|V|)在内存中循环而无递归地对图形进行排序”，但有人告诉我什么是过度杀伤力。

免责声明：我是程序员，而不是数学家，因此在某些地方您可能并且应该踢错语言。

任务的实质

我将分部分分析问题的措辞和我想分享的解决方案。

拓扑排序是有向无环图的顶点的排序，其中从中引出边的每个顶点比该边进入的顶点更早出现。 这里有两个重要的细微差别：一个图可以具有多个这样的排序，并且仅适用于非循环图。 数学家不在乎，但是程序员有时想要确定性，而不仅仅是“对不起，这里有一个循环，您不会被理清”。

因此，我们增加了稳定性要求：一对顶点之间的顺序不是由图的边缘指定的，应由这些顶点到达算法输入的顺序来确定。 结果，重复的排序不会改变顶点的顺序。

由于没有递归，一切都很简单，计算机比图灵机明显更弱，并且内存（尤其是堆栈）受到限制。 因此，在应用编程中，通常迭代算法优于递归算法。

最后，如果图中有循环 ，我将定义所谓的“拓扑”排序。 这是顶点的排序，如果每个循环都被一个顶点替换，并且根据稳定性要求，循环本身的顶点以原始顺序彼此相对放置，则这与真正的拓扑排序是一致的。

现在，所有这些垃圾我们将尝试起飞，我将在帖子开头指出的时间和内存限制的范围内进行所有操作。

寻找解决方案

如果您查看现有的用于拓扑排序的算法 （ Kahn算法 ， 深度搜索 ），结果发现它们全都存在，如果有循环，请说“我不能”，然后停止工作。

因此，让我们从另一方面讲，算法可以对周期进行一些可理解的操作。 例如， 找到它们。 在Wikipedia中列出的用于在图形中查找循环的算法中，引起关注的是Taryan算法 。 它包含一个有趣的注释，即该算法作为副产品产生图的逆拓扑排序：

尽管每个强连接组件中的节点顺序没有什么特别的，但是该算法的一个有用特性是，在其任何后续组件之前都不会标识强连接组件。 因此， 确定强连接的组件的顺序构成了由强连接的组件形成的DAG的反向拓扑排序 。

的确，该算法是递归的，尚不清楚其稳定性如何，但这显然是朝着正确方向发展。 仔细阅读Wikipedia可以发现对以下文章的引用：由大卫·皮尔斯（David Pierce）同志创作的一种节省空间的算法，用于查找强连接的组件 ，该算法不仅具有强制性算法，而且与经典算法相比，还减少了内存需求Tarjan的算法。 额外的好处是该算法在Java中的实现 。 必须服用！


因此，我们在输入处有一个顶点列表，并且（由于使用了Pierce）在输出中该顶点所属的强连通性分量的某个索引。 下一步是根据顶点的序列号对顶点进行稳定排序。 有一种用于此类任务的算法，称为计数排序 ，该算法在O(n)时间内执行此操作。

在将算法收集到堆中的过程中，事实证明，对它进行反向拓扑排序是很自然的事实，实际上是从Taryan向外进行-然后，图的相邻分支（它们之间没有顺序关系）将向后编号，因此图的各部分将不会彼此之间有任何联系，结果却是相反的顺序...

答案

所以最终的解决方案是：

1. 我们编号原始列表的顶点。 O(|V|)
2. 我们根据边缘所到达的顶点的数量对每个顶点的边缘进行排序。 O(|e| log |e|)
3. 使用Pierce算法，我们可以找到并编号强连接的组成部分。 O(|V|)
4. 通过使用计数排序，我们根据接收到的强连接组件的数量对顶点进行排序。 O(|V|)

GitHub代码，Java，公共领域 。 可以注意到，为了确保排序的稳定性，对Pierce算法进行了一些修改，并以相反的顺序绕过了顶点。

但是为什么呢？

现在是背景，为什么需要所有这些。 在加载/卸载动态库（.so）时，glibc需要确定以哪种顺序初始化静态变量。 变量相互依赖，取决于不同的功能等。 总的来说，所有这些形成了一个图表，其中存在循环并且必须对其进行排序。

曾几何时，执行O(n^2)任务的次优代码参与了此任务。 总的来说，这并没有真正打扰到任何人，直到2012年，人们才发现代码无法正常工作，并且在某些情况下是错误的。

来自RedHat的严酷的人思考，思考并从上方弄乱了几个周期。 问题案例已修复，但是该算法开始适用于O(n^3) ，这已经变得很明显，并且在某些应用程序上开始花费数十秒钟，这在2013年是一个错误 。 此外，该错误的作者发现了O(n^3)算法也被误认为的情况 。 他建议使用Taryan算法，尽管从未设计过带有修正的补丁。

随着时间的流逝，glibc毫不留情地放慢了速度，2015 年又尝试修复该算法 。 不幸的是，没有成功，算法被选择为O(n^2) ，除了混淆了图的分支，在它们之间没有定义顺序。

今天是2019年，glibc仍在放缓。 从我解决该问题花了多少时间来看，我将其彻底解决的机会大大低于100％。 由于事实是C语言在没有IDE支持的情况下以GNU编码风格的代码疯狂地运行了测试程序（“如果您想再次运行测试，只需删除相应的.out文件”），就会使情况更加恶化。 为了使glibc查看您的补丁程序，您需要执行版权分配过程，正确发行补丁程序，魔鬼知道还有什么。 因此，为了至少消除发明解决该问题的算法的问题，撰写了这篇文章。