8

我试图找到一种空间要求适中的快速算法来解决以下问题。

对于 DAG 的每个顶点，在 DAG 的传递闭包中找到其入度和出度的总和。

鉴于此 DAG：

来自维基百科的 DAG

我期待以下结果：

Vertex #   Reacability Count  Reachable Vertices in closure
   7             5            (11, 8, 2, 9, 10)
   5             4            (11, 2, 9, 10)
   3             3            (8, 9, 10)
  11             5            (7, 5, 2, 9, 10)
   8             3            (7, 3, 9)
   2             3            (7, 5, 11)
   9             5            (7, 5, 11, 8, 3)
  10             4            (7, 5, 11, 3)

在我看来，这应该是可能的，而无需实际构建传递闭包。我无法在网上找到任何能准确描述这个问题的东西。我有一些关于如何做到这一点的想法，但我想看看 SO 人群能想出什么。

4

5 回答 5

2

对于一个确切的答案，我认为很难击败 KennyTM 的算法。如果您愿意接受近似值，那么坦克计数方法（http://www.guardian.co.uk/world/2006/jul/20/secondworldwar.tvandradio）可能会有所帮助。

为每个顶点分配一个 [0, 1) 范围内的随机数。使用像 polygenelubricants 之类的线性时间动态程序来计算每个顶点 v 可从 v 到达的最小数量 minreach(v)。然后将 v 可到达的顶点数估计为 1/minreach(v) - 1。为了获得更好的准确性，请重复几次，并在每个顶点取平均值。

于 2010-03-06T17:59:09.103 回答
1

对于每个节点，使用 BFS 或 DFS 来查找可达性。

对相反的方向再做一次以找到不可达性。

时间复杂度：O(MN + N 2 )，空间复杂度：O(M + N)。

于 2010-03-06T09:04:32.220 回答
1

我已经为这个问题构建了一个可行的解决方案。我的解决方案基于对拓扑排序算法的修改。下面的算法只计算传递闭包中的入度。可以以相同的方式计算出度，将边缘反转并将每个顶点的两个计数相加以确定最终的“可达性计数”。

for each vertex V
   inCount[V] = inDegree(V)   // inDegree() is O(1)
   if inCount[V] == 0
      pending.addTail(V)

while pending not empty
   process(pending.removeHead())

function process(V)
   for each edge (V, V2)
      predecessors[V2].add(predecessors[V])   // probably O(|predecessors[V]|)
      predecessors[V2].add(V)
      inCount[V2] -= 1
      if inCount[V2] == 0
          pending.add(V2)
   count[V] = sizeof(predecessors[V])         // store final answer for V
   predecessors[V] = EMPTY                    // save some memory

假设集合操作是 O(1)，这个算法在 O(|V| + |E|) 中运行。然而，集合并集操作更有可能predecessors[V2].add(predecessors[V])使它变得更糟。集合并集所需的额外步骤取决于 DAG 的形状。我认为最坏的情况是 O(|V|^2 + |E|)。在我的测试中，该算法显示出比我迄今为止尝试过的任何其他算法更好的性能。

此外，通过处理完全处理的顶点的前驱集，该算法通常比大多数替代方案使用更少的内存。然而，上述算法的最坏情况下的内存消耗确实与构造传递闭包的内存消耗相匹配，但对于大多数 DAG 而言，情况并非如此。

于 2010-03-11T04:53:44.423 回答
0

天哪，错了！对不起！

我会留下这个，直到有一个好的替代方案可用。如果可能，请随时讨论和扩展 CW-ed。

使用动态规划。

for each vertex V
   count[V] = UNKNOWN
for each vertex V
   getCount(V)


function getCount(V)
   if count[V] == UNKNOWN
      count[V] = 0
      for each edge (V, V2)
        count[V] += getCount(V2) + 1          
   return count[V]

这是O(|V|+|E|)与邻接列表。它只计算传递闭包中的出度。要计算入度，请getCount在反转边缘的情况下调用。要获得总和，请将两个调用的计数相加。

要了解为什么会这样O(|V|+|E|)，请考虑以下情况：每个顶点V将被准确地访问1 + in-degree(V)一次：一次直接在 上V，一次在每条边上(*, V)。在随后的访问中，getCount(V)，简单地返回记忆count[V]中的O(1)。

另一种看待它的方法是计算每条边将跟随多少次：恰好一次。

于 2010-03-06T07:23:30.623 回答
0

我假设您有一个所有顶点的列表，并且每个顶点都有一个id和一个您可以直接从中访问的顶点列表。

然后，您可以添加另一个包含您也可以间接到达的顶点的字段（或者您可以表示该字段）。我将在递归深度优先搜索中执行此操作，在各个到达节点的字段中记住结果。作为一种数据结构，您可能会使用某种允许有效删除重复项的树。

不可达性可以通过添加反向链接单独完成，但也可以与不可达性在同一遍中完成，通过累积当前的外延节点并将它们添加到已到达节点的相应字段中。

于 2010-03-06T11:44:13.330 回答