图的传递闭包定义在这里:http://mathworld.wolfram.com/TransitiveClosure.html
当顶点数为n时,可以很容易地在O(n^3)的时间内完成。我想知道是否可以在O(n^2)的时间内完成。
图的传递闭包定义在这里:http://mathworld.wolfram.com/TransitiveClosure.html
当顶点数为n时,可以很容易地在O(n^3)的时间内完成。我想知道是否可以在O(n^2)的时间内完成。
不,我认为没有一个O(n2)的算法可以解决这个问题。如果存在这样的算法,那么你也可以用O(n2)的时间解决所有对最短路径问题,但事实并非如此。我能想到的渐进最快的算法是使用斐波那契堆实现的Dijkstra最短路径算法(在不太密集的图中为O(n2log n))。
嗯,我找到了一个计算传递闭包的算法,其预期运行时间为O(n^2)。
鉴于这个问题:
你能想出一个O(kn^2 + m)的传递闭包/约简算法吗?其中k是传递闭包/约简中缺失/额外边的数量?
对于那些比我们更多思考这些问题的人来说,这仍然被认为是一个未解决的问题,我会说“我不知道”。
(但如果你解决了它并想要获得博士学位,我知道那个算法。)