logo标签列表

图的直径算法？

algorithmgraphlanguage-agnosticgraph-algorithm
19

如果你有一个图，需要找到它的直径（即两个节点之间的最大距离），如何在O(log v * (v + e))复杂度内实现。

维基百科上说可以使用Dijkstra算法和二叉堆来实现。但我不明白这是如何工作的，有人能解释一下吗？

或者展示一个伪代码？

Dijkstra算法无法找到图的直径；它只能找到从某个节点到图中每个其他节点的距离。您是否有任何资源可以证明可以使用Dijkstra算法来完成此操作？ - templatetypedef
3
http://cs.stackexchange.com/questions/194/the-time-complexity-of-finding-the-diameter-of-a-graph - omega
1
链接中没有提到您应该使用Dijkstra算法来完成此操作。 - templatetypedef
边缘是否带权重？ - MAK
它们没有加权。 - omega
显示剩余5条评论
11个回答
19

虽然我已经晚了一年，但我不认为这些答案中有任何一个是正确的。OP在评论中提到边缘是无权重的；在这种情况下，最佳算法运行时间为O(nω log n)（其中ω是矩阵乘法的指数；目前由Virginia Williams上限限制在2.373）。

该算法利用了无权图的以下属性。让A成为具有每个节点自环的图的邻接矩阵。那么（Ak）ij为非零当且仅当d(i, j) ≤ k。我们可以利用这个事实通过计算Ak的log n个值来找到图直径。

算法如下：让A成为具有每个节点自循环的图的邻接矩阵。将M0 = A。当Mk包含至少一个零时，计算Mk+1 = Mk2。

最终，您会找到一个所有条目都非零的矩阵MK。根据上述属性，我们知道K ≤ log n；因此，我们迄今为止只进行了O(log n)次矩阵乘法。现在，我们可以继续在MK = A2K和MK-1 = A2K-1之间进行二进制搜索。以下是如何设置B等信息。

设置DIAMETER = 2k-1。对于i =（K-2 ... 0），执行以下测试：

将B乘以Mi，并检查结果矩阵是否为零。如果发现任何零，则将B设置为此矩阵乘积，并将2i添加到DIAMETER中。否则，不执行任何操作。

最后，返回直径。

作为一个次要的实现细节，可能需要在每次矩阵乘法执行后将矩阵中所有非零元素设置为1，这样值不会变得过大和难以在短时间内书写。
4
不错的方法。有几个小问题：（1）我认为，在i达到0之后，B中仍然可能没有条目，如果是这种情况，则直径为2^K（即原始平方循环恰好找到最小的直径）。 （2）你可以使用位AND和OR代替乘法和加法，以确保单元格值不会变得笨重。 （3）在邻接矩阵进行log2（n）次平方运算之后，要么所有条目都不为零，要么该图在一开始就没有连通。 - j_random_hacker
11

对于一个一般的图 G=(V,E)，目前没有已知时间复杂度为 O(log V * (V + E)) 的算法来计算直径。

目前最好的解决方案是 O(V*V*V)，比如使用 Floyd Warshall 算法计算所有最短路径。

对于稀疏图，即当 E 在 o(N*N) 时，Johnson 算法可以用 O(V*V*log(V)+V*E) 实现更好的时间复杂度。

如果您的图具有特定的性质，例如无环（树），则可以获得更好的效果。

所以坏消息是，在一般情况下 Dijkstra 不足以解决问题...

2

图形描述 - 无向且无权，n个节点，m条边。对于图的直径，我们需要计算所有节点之间的最短路径。在无向且无权图中，可以使用BFS算法来计算源节点到所有其他节点的最短路径。对于1个节点，时间复杂度为O(n + m)。因为我们需要对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的矩阵来存储任意两个节点之间的最短路径。我们使用一个名为flag的字典，其中包含true或false值，表示顶点是否已被访问。对于每次BFS迭代，我们将此字典初始化为全部false。我们使用队列Q执行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
2
假设图形是无权的，则以下步骤可以在O（V *（V + E））中找到解决方案，其中V是顶点数，E是边数。
让我们定义两个顶点u、v之间的距离为u和v之间的最短路径长度。用d(u, v)表示。 将一个顶点v的离心率定义为e(v) = max {d(u, v) | u ∈ V(G)} （G图的顶点集为V(G)） 将直径(G)定义为max{e(v) | v ∈ V(G)}
现在是算法：
1- 对于V(G)中的每个顶点v，运行BFS(v)，并构建每个顶点到其他顶点的距离的二维数组。（在BFS algorithm中计算每个顶点到其他顶点的距离很容易）
2- 从步骤1中创建的二维数组中计算每个顶点的e(v) 3- 通过从步骤2中找到的最大e(v)来计算diameter(G)

现在分析这个算法，很容易看出它被第一步支配，该步骤的时间复杂度为 O(V*(V+E))

阅读维基百科关于直径的部分

另一个时间复杂度为线性O(V+E)的算法： 1- 在任意随机顶点v∈V(G)上运行BFS 2- 选择距离最大的顶点u 3- 再次在那个顶点u上运行BFS 4- 直径是从步骤3生成的最大距离

第二个函数找到的是伪周边顶点，不一定是真正的周边顶点。 - user1529540
1
如eci所提到的，其中一种解决方案是使用Floyd-Warshall算法。如果你需要它的代码，可以在这里找到C++版本。
1
Boost BGL有一个名为"rcm_queue"的小型扩展双端队列类，可以通过简单的广度优先搜索找到顶点的偏心率，意味着复杂度为O(E)。

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

由于直径可以通过遍历所有顶点的离心率来计算，因此可以使用O（V * E）的复杂度计算图的直径。

特别是对于一个非常稀疏的图，其中deg（G）<<

我没有研究Floyd Warshall算法。我只处理了一个具有> 5,000,000个顶点但最高顶点度数小于15的图，并认为这应该优于具有V * V * log（V）复杂度的算法。

编辑

当然，这仅适用于无向图，而不是负加权（甚至仅限于未加权？我现在不确定）

你能提供一个简单的例子来说明如何使用它吗？ - Mehmet Fide
0
首先，您需要找到图形的凸包（查找它的时间复杂度为O(nh)，其中h是凸包上节点的数量）。直径的点将位于凸包上，因此问题将简化为在h个点中查找最远的点。因此，总的时间复杂度将为O(nh+h*h)。
4
我认为这个问题涉及到一个抽象图形。您的回答涉及到平面上的一些点，并查找它们之间的最大距离，这是不同的问题。例如，抽象图形不必满足三角不等式。此外，您算法的总复杂度将为O(nh+hh)，这比O(nh^3)小。 - eci
0

实际上，如果图形非常大，您将需要使用Dijkstra算法来查找最短距离。因此，这取决于OP的图形有多少个节点。

0

直径通常指图形G(V,E)中任意两个节点之间的最大最短距离，我们称之为δ(a,b)。让d成为BFS源的距离列表。让s成为G中的任何节点。BFS(G,s)将生成d值，其中d[a]、d[b]中有最大的d值。如果它们共享此值，则已找到a和b。否则，假设a单独作为最大值。然后运行BFS(G,a)，最大的d值将是d[b]，从而在O(V+E)+O(V+E)=O(V+E)时间内找到δ(a,b)。

这个方法的有效性在于第一次广度优先搜索将确定 a、b 或两者都是。我们可以通过反证法来证明这是可能的。 证明更好地陈述在这个来源中：https://walkccc.me/CLRS/Chap22/22.2/

0

你不能只是单调地将 A 不断提高到下一个幂，并跟踪哪些 (i,j) 在某个 A^k 中具有非零条目吗？一旦所有的 i,j 在先前计算的 A^k 中都有了非零值，那么你所在的 k 就是图的直径。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接