计算图的传递闭包所需的渐近运行时间？
图的传递闭包定义如下： http://mathworld.wolfram.com/TransitiveClosure.html
这在 O(n^3) 中很容易实现，其中 n 是顶点数。 我想知道是否可以在 O(n^2) 时间内完成。
The transitive closure of a graph is defined e. g. here: http://mathworld.wolfram.com/TransitiveClosure.html
It is easily possible in O(n^3), where n is the number of vertices. I was wondering if it can be done in time O(n^2).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
没有。 我认为没有 O(n2) 算法。 我希望如果存在这样的算法，您也可以在 O(n2) 中解决所有对最短路径问题，但事实并非如此。 我能想到的渐近最快算法是使用斐波那契堆 (O(n2log n) 实现 Dijkstra 最短路径算法不是很密集的图表）。
Nope. I don't think there is a O(n2) algorithm for it. I would expect if such an algorithm existed, you could solve all pair shortest paths problem in O(n2) too, which is not the case. The asymptotically fastest algorithm I can think of is an implementation of Dijkstra's shortest path algorithm with a Fibonacci heap (O(n2log n) in not very dense graphs).
唔。 我找到了一种算法，可以在 O(n^2) EXPECTED 运行时间内计算传递闭包。
Hmm. I found an algorithm that computes the transitive closure in O(n^2) EXPECTED run time.
鉴于此：
对于那些比我们思考这些事情更多的人来说，这仍然是一个悬而未决的问题，我会说“我不知道”。
（但如果你解决了这个问题并想要获得博士学位，我知道那个算法。）
Given that this:
Is still considered an open question by people who think about these sorts of things more than we do, I'd say "I don't know".
(But if you solve it and want a PhD, I know that algorithm.)