5

我被要求写一个有效的算法来找到有向图中的所有顶点，这些顶点从给定顶点到它们的路径长度是均匀的。

这是我想到的：

（与 DFS 的“访问”算法非常相似）

Visit(vertex u)

     color[u]<-gray
     for each v E adj[u]
       for each w E adj[v]
            if color[w] = white then
                     print w
                     Visit(w)

我认为它有效，但我很难计算它的效率，特别是当图表带有周期时。你可以帮帮我吗？

4

2 回答 2

6

如果我可以提出替代方案 -我会减少问题并使用 DFS 而不是修改 DFS。

给定一个图G = (V,E)，创建一个图G' = (V,E')，其中E'={(u,v) | there is w in V such that (u,w) and (w,v) are in E)
换句话说 - 我们正在创建一个图 G'，当且仅当从 u 到 v 的路径长度为 2 时，它具有边 (u,v)。

鉴于该图，我们可以推导出以下算法[高级伪代码]：

  1. 从 G 创建 G'
  2. 从源运行 DFS on G' s，并标记相同的节点 DFS 标记。

解的正确性和时间复杂度分析：

复杂性： 复杂性显然是O(min{|V|^2,|E|^2} + |V|)，因为第 1 部分 - 因为min{|E|^2,|V|^2}G' 中最多有边，所以第 2 步的 DFS 运行在O(|E'| + |V|) = O(min{|V|^2,|E|^2} + |V|)

正确性：
如果算法发现有一条从v0到vk的路径，那么从DFS的正确性来看——在G'上有一条路径v0->v1->...->vk，所以有一条v0->v0'->v1->v1'->...->vk偶数的路径G 上的长度。 如果从到
上存在一条长度相等的路径，就让它成为。then是 上的路径，将由 DFS 找到 - 从 DFS 的正确性来看。Gv0vkv0->v1->...->vkv0->v2->...->vkG'

附带说明：
减少问题而不是修改算法通常不易受到错误的影响，并且更容易分析和证明正确性，因此您通常应该尽可能选择这些而不是修改算法。

编辑：关于您的解决方案：嗯，分析它表明它们几乎相同 - 除了我E'作为预处理生成，而您在每次迭代中动态生成它。
由于您的解决方案正在动态生成边缘 - 它可能会不止一次地做一些工作。然而，|V|由于每个顶点最多被访问一次，所以它在大多数情况下更多地被限制在工作中。
为简单起见，为您的解决方案 |E| = O(|V|^2)提供运行时间的总上限。它也是一个下界，看一个clique的例子，在每个节点的每个节点，算法都会生成所有的可能性，并且O(|V|^3)
visit()O(|V|^2)visit()一种可能性，因为我们准确地访问|V|节点，我们得到总运行时间Omega(|V|^3)
因为我们发现解决方案是O(|V|^3)和Omega(|V|^3)，所以总运行时间是Theta(O(|V|^3))

于 2012-04-17T12:16:39.390 回答
1

对于每个无向图 G(V,E)，我们应该在以下情况下将上述图重建为二分图 G'(V',E')：

  • V' = V1 ∪ V2
  • E'={(u1,v2):(u,v)∈E, u1∈V1, v2∈V2}
  • V1={v1: v∈V}
  • V2={v2: v∈V}

例如图表

给定图

变成

二分图

在这个图（二分图）上，我们应该运行 BFS 算法 - BFS(G',S1')。运行 BFS(G',S1') 后，我们应该返回包含最短偶数路径长度 δ(s1,u1) 的数组 d

于 2020-04-22T20:41:33.103 回答