5

有一个有向图（不一定连接），其中一个或多个节点被区分为源。从任何一个来源可访问的任何节点都被视为“点亮”。现在假设其中一条边被删除。问题是要确定以前点亮和不再点亮的节点。

我想可以考虑像城市电力系统这样的类比。

4

5 回答 5

7

这是一个“动态图可达性”问题。以下论文应该有用：

一种具有几乎线性更新时间的有向图的完全动态可达性算法。利亚姆·罗迪蒂，乌里·兹维克。计算理论，2002。

这给出了一种算法，在可能的循环图上具有 O(m * sqrt(n)) 时间更新 ( amortized ) 和 O(sqrt(n)) 时间查询（其中 m 是边数，n 是节点）。如果图是非循环的，这可以改进为 O(m) 时间更新（amortized）和 O(n/log n) 时间查询。

考虑到问题的具体结构，或者以空间换时间，你总是有可能做得比这更好。

于 2009-01-05T16:12:43.300 回答
1

如果不只是“点亮”或“未点亮”，您将保留一组节点，节点从中通电或点亮，并将具有空集的节点视为“未点亮”，将具有非空集的节点视为“ lit”，那么删除一条边只需要从目标节点的集合中删除源节点。

编辑：忘记了这一点：如果您删除集合中的最后一个 lit-from-node，遍历边缘并从他们的集合中删除您刚刚“未点亮”的节点（也可能从那里遍历，依此类推）

EDIT2（对 tafa 的改写）：首先：我误读了原始问题，并认为它指出对于每个节点，它已经知道是点亮或未点亮的，正如我现在重新阅读的那样，没有提及。

但是，如果您为网络中的每个节点存储一个包含它被照亮的节点的集合，您可以轻松地从移除的边缘遍历图形并修复任何照亮/未照亮的引用。因此，例如，如果我们有这样的节点 A、B、C、D：（ascii 艺术的蹩脚尝试）

A -> B >- D
 \-> C >-/

然后在节点 A 存储它是一个源（因此它自己被点亮），在 B 和 C 中你会存储它们被 A 点亮，在 D 中你会存储它被 A 和 C 点亮.

然后说我们从 B 到 D 删除边：在 D 中，我们从 lit-source-list 中删除 B，但它仍然亮着，因为它仍然被 A 点亮。接下来说我们从 A 到 C 删除边之后：A从 C 的集合中移除，因此 C 不再被点亮。然后我们继续遍历起源于 C 的边，并从 D 的集合中移除 C，该集合现在也是未点亮的。在这种情况下，我们完成了，但如果集合更大，我们就从 D 继续。

该算法只会访问直接受到删除或添加边影响的节点，因此（除了每个节点所需的额外存储）应该接近最优。

于 2009-01-05T15:48:06.547 回答
1

这是你的作业吗？

最简单的解决方案是在原始图上执行 DFS ( http://en.wikipedia.org/wiki/Depth-first_search ) 或 BFS ( http://en.wikipedia.org/wiki/Breadth-first_search )从源节点。这将为您提供所有原始点亮的节点。

现在删除有问题的边缘。再次执行 DFS。您可以选择仍然亮着的节点。

输出出现在第一组而不是第二组的节点。

这是一种渐近最优算法，因为您执行两个 DFS（或 BFS），它们占用 O(n + m) 时间和空间（其中 n = 节点数，m = 边数），这决定了复杂性。您至少需要 o(n + m) 时间和空间来读取输入，因此该算法是最优的。

现在，如果您想删除多个边缘，那会很有趣。在这种情况下，我们将讨论动态数据结构。这是你想要的吗？

编辑：考虑到评论：

  • 未连接不是问题，因为在搜索期间将无法到达无法访问的连接组件中的节点
  • 有一种聪明的方法可以同时从所有节点执行 DFS 或 BFS（我将描述 BFS）。您只需将它们全部放在堆栈/队列的开头即可。

BFS 的伪代码，用于搜索从任何起始节点可到达的所有节点：

队列 q = [所有起始节点]
while (q 不为空)
{
   x = q.pop()
   forall（x 的 y 邻居）{
      if (y 没有被访问) {
         访问[y] = true
         q.push(y)
      }
   }
}

将队列替换为堆栈，您将获得一种 DFS。

于 2009-01-05T15:53:58.800 回答
0

图表有多大和连接程度如何？您可以存储从源节点到所有其他节点的所有路径，并查找到该节点的所有路径都包含删除边之一的节点。

编辑：稍微扩展一下这个描述

从每个源节点执行 DFS。跟踪生成到每个节点的所有路径（作为边，​​而不是顶点，所以我们只需要知道所涉及的边，而不是它们的顺序，因此我们可以使用位图）。为每个节点记录从源到节点的路径数。

现在迭代路径。删除包含已删除边的任何路径并减少该节点的计数器。如果一个节点计数器减到零，它就亮了，现在不亮了。

于 2009-01-05T15:45:57.490 回答
0

在构建图形时，我会保留边上连接的源节点的信息。（例如，如果边与源 S1 和 S2 有连接，则其源列表包含 S1 和 S2 ）并使用输入边的信息创建节点和输出边缘。当一条边被删除时，通过考虑该节点的输入边来更新该边的目标节点的输出边。并使用 DFS 或 BFS 遍历更新边的所有目标节点。（如果是循环图，请考虑标记）。在更新图表时，也可以找到没有任何边的节点，但有源连接（点亮->未点亮节点）。但是，如果您想同时删除多个边，这可能不是一个好的解决方案，因为这可能会导致一次又一次地遍历相同的边。

于 2009-01-05T16:13:21.410 回答