算法图的直径?(Algorithm for diameter of graph?)

2019-07-23 14:42发布

如果你有一个图表,需要找到它的直径(这是两个节点之间的最大距离),你怎么能在做到这一点O(log v * (v + e))的复杂性。

维基百科说,你可以用做Dijkstra's algorithmbinary heap 。 但我不明白这是如何工作。 有人能解释一下吗?

或显示一个伪?

Answer 1:

对于一般的图形G=(V,E)没有O(log V * (V + E))用于计算直径已知的时间复杂度的算法。 目前最好的解决办法是O(V*V*V)例如,通过计算与弗洛伊德沃肖尔的算法所有最短路径。 对于稀疏图,即当Eo(N*N)约翰逊的算法为您提供了O(V*V*log(V)+V*E)一个更好的时间复杂度。

如果你的图具有一定的属性,如无环(树),你可以得到更好的。

所以坏消息是,戴克斯特拉将不足以在一般情况下...



Answer 2:

我知道我是一个今年晚些时候线程,但我不相信这些答案都是正确的。 OP,所述边缘是未加权的评论中提到; 在这种情况下,最好的算法在$运行O(N ^ {\欧米加})\日志n $的时间(其中$ \欧米加$为矩阵乘法的指数;目前在上部$ 2.373 $由弗吉尼亚威廉姆斯界定)。

该算法利用加权图的下列财产。 让$ A $是具有添加的自循环每个节点的图的邻接矩阵。 然后$(A ^ k)的_ {IJ} $非零当且仅当$ d(I,J)\文件ķ$。 我们可以利用这一点,通过计算$ A-1K-$的$ \日志N $值找到图形直径。

这里的算法是如何工作的:让$ A $是具有自我添加循环每个节点的图的邻接矩阵。 设置M_0 $ = A $。 虽然$ $ M_k含有至少一个为零,计算$ M_ {K + 1} = M_ {K} ^ 2 $。

最后,你会发现一个矩阵$ M_ {K} $所有非零项。 我们知道,$ķ\乐\登录上述讨论的财产N $; 因此,我们已经完成矩阵乘法仅Ø$(\ log n)的$倍为止。 现在,我们可以通过$ M_ {K} = A ^ {2-1K-} $和$ {M_ K-1} = A ^ {2 ^ {K-1}} $之间的二进制搜索继续。 集合$ B = M_ {K-1} $如下。

设置直径= $ 2 ^ {K-1} $。 对于$ I =(K-2 \点0)$,执行下面的测试:

乘$ B $ $通过M_ {I} $并检查零结果矩阵。 如果我们发现任何零,然后设置$ B $这个矩阵的产品,并添加$ 2 ^ I $直径。 否则,什么都不做。

最后,返回直径。

作为一个次要的实现细节,它可能有必要在矩阵中所有非零项设置为$每个矩阵相乘后1 $进行,从而使价值没有得到过大而笨重写下来的少量时间。



Answer 3:

升压BGL有一个名为“rcm_queue”与顶点的偏心可以通过简单的广度优先搜索发现,这意味着O(E)的复杂性小的扩大双端队列类。

http://www.boost.org/doc/libs/1_54_0/boost/graph/detail/sparse_ordering.hpp

由于直径可以通过去在所有顶点的偏心进行计算,一个可与复杂度O(V * E)计算的曲线图的直径。

特别是对于非常稀疏图有度(G)<<< V,我没有找到更好的运行任何东西。

我没有看到弗洛伊德Warshall算法。 我只是在处理与> 5.000.000顶点的图,但小于15和思想的任何顶点度最高,这或许应该超越与V * V *日志(V)的复杂的算法。

编辑

可以肯定,这只能用无向图,而不是消极的加权(甚至只未加权?我不知道ATM)的作品



Answer 4:

作为ECI提到的,解决方案之一是使用Floyd-Warshall算法。 如果你需要它的代码,它的C ++版本,可以发现在这里 。



Answer 5:

首先,你需要找到图形的凸包 (发现它是O(NH),其中h是船体节点的数量)。 直径的点将位于凸包,因此该问题将减少到在H点发现的最远点。 因此,总顺序将是O(NH + H * H)。



Answer 6:

实际上,如果图形是非常大的,你需要使用Dijkstra算法,以便找到最短的距离。 所以,这取决于OP的图形多少节点了。



Answer 7:

假设图是未加权的,则下面的步骤可以找到在O溶液(V *(V + E)),其中V是顶点的数目,E是边的数量。

我们的算法:

1-对于V各自顶点v(G)运行BFS(v)和从每个顶点到其他建立的距离的2维阵列。 (计算从每个顶点到他人的距离很容易在做BFS算法 )

2-计算E(V),用于通过将来自步骤2查找最大E(V)从2维阵列的每个顶点在步骤1 3-计算直径(G)中创建

我们分析这个算法,可以很容易地看到,它是由第一个步骤,是O的支配(V *(V + E))

阅读本篇关于维基百科直径

在线性时间为O(V + E)1-运行BFS运行另一算法上的任何随机顶点v∈V(G)2-对顶点再次拾取顶点u与最大距离3-运行BFSÚ4-直径是最大距离生成表单步骤3



Answer 8:

图描述-无向无权,n个节点,m条边在曲线图的直径,我们需要计算所有节点对之间的最短路径。 源节点到所有其他节点之间的最短路径可以使用BFS算法无向和非加权曲线图来计算。 时间复杂度是O(N + M)为1级的节点。 在这里,因为我们需要为n个节点做BFS,找到所有对节点之间的最短路径的总的时间复杂度变为O(N(N + M))。 由于有N(N-1)/ 2对节点,所以我们有N(N-1)中的所有节点之间的最短路径的/ 2的值。 对于直径,我们需要获得这些值的最大值,这又是O(N * N)。 所以,最终的时间复杂度变为:

       O(n(n + m)) + O(n*n) = O(n(2n + m)) = O(n(n + m))

对于伪代码让所有节点对之间的最短路径。 我们使用的是矩阵命名Shortest_paths存储任意两个节点对之间的最短路径。 我们正在使用的有值true或false指示顶点是否已被访问或没有字典命名的标志。 对于BFS的每一次迭代,我们初始化这个字典全是假的。 我们用一个队列Q可履行我们的BFS。 算法BFS(所有节点)

Initialize a matrix named Shortest_paths[n][n] to all -1. 
    For each source vertex s
        For each vertex v
            Flag[v] = false
        Q = empty Queue
        Flag[s] = true
        enQueue(Q,s)
        Shortest_paths[s][s] = 0
        While Queue is not empty
            Do v = Dequeue(Q)
            For each w adjacent to v
                Do if flag[w] = false
                    Flag[w] = true
                    Shortest_paths[s][w] = Shortest_paths[s][v] + 1
                    enQueue(Q,w) 
    Diameter = max(Shortest_paths)
    Return Diameter


Answer 9:

这只能与不加权的图形发生。 凡BFS给邻最短路径树(V + E),你重复相同的伏电源。



文章来源: Algorithm for diameter of graph?