图的传递闭包定义为e。 G。这里:http://mathworld.wolfram.com/TransitiveClosure.html
在O(n ^ 3)中很容易实现，其中n是顶点数。我想知道是否可以在时间O(n ^ 2)内完成。
最佳答案
没有。我认为没有O(n2)算法。我希望如果存在这样的算法，那么您也可以解决O(n2)中的所有对最短路径问题，事实并非如此。我能想到的渐近最快的算法是Dijkstra最短路径算法的斐波那契堆(在不太稠密的图中为O(n2log n))的实现。
关于language-agnostic - 计算图的传递闭合所需的渐近运行时间？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/703531/