查找DAG所有顶点的可达性计数

Question

我正在寻找一种具有适度空间需求的快速算法来解决以下问题。

对于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社区能想出什么。

- ChrisH

---

作为顶点7，在传递闭包中，入度为0，出度为5，如何得到“6”个可达性计数？同样对于顶点5（如何获得4而不是3），而对于顶点3，您想要的3似乎是正确的（与顶点5相同）。在我们深入了解您的要求之前，请详细解释应该如何获得那些看起来奇怪的数字（入度和来自哪些节点；出度和到哪些节点）。 - Alex Martelli

顶点7是一个打字错误，正在编辑... 顶点5在TC中有(11, 2, 9, 10)作为后继。 顶点3在TC中有(8, 9, 10)作为后继。 - ChrisH

我已经在例子中添加了每个源顶点的可达顶点集合。 - ChrisH

您能否澄清一下您的需求：即，为什么您需要小空间要求？您的DAG是否隐式表示？还是稀疏但具有密集的传递闭包？（否则，您将无论如何存储DAG，并且标准的传递闭包算法不会改变空间渐近性） - jkff

我的当前实现确实构建了完整的传递闭包，我正在尝试在时间和空间上进行改进。我并不需要更多的内存，但我想使用更少的内存。我的DAG的许多实例将相对稀疏，但具有密集的传递闭包。生成DAG模型数据的过程偏向于高度链接和连接的DAG。 - ChrisH

Answer 1

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

将每个顶点分配一个在[0, 1)范围内的随机数。使用像polygenelubricants一样的线性时间动态规划来计算每个顶点v可达的最小数量minreach(v)。然后估计从v可达的顶点数为1/minreach(v)-1。为了更准确，重复几次，并在每个顶点处取平均数的中位数。

- user287792

---

虽然我正在寻找一个确切的答案，但我喜欢你的帖子。谢谢你的文章，非常有趣，而且计算坦克数量的方法很好。+1，因为你有独特的思维方式。 - ChrisH

@user287792 我认为这个方法不可行。以一个顶点为例，如果 $X$ 在 [0,1] 中随机分布，则 $1/X$ 的期望值应该是未定义的，即使您的方法假设它应该有期望值为二。 - exfret

Answer 2

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

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来说并非如此。

- ChrisH

Answer 3

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

再次对反向方向执行此操作以查找可到达性。

时间复杂度：O（MN + N ^ 2），空间复杂度：O（M + N）。

- kennytm

Answer 4

哎呀，出错了！对不起！

在有更好的替代方案之前，我会保留这个。标记为CW，所以如果可能的话，请随意讨论和扩展。

---

使用动态规划。

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)将在O(1)时间内简单地返回记忆化的count[V]。

另一种看待这个问题的方式是计算每条边将被跟随多少次：恰好一次。

- polygenelubricants

---

这是否也包括不可达性？例如，DAG A -> B -> C 对于所有3个节点应该给出结果2。 - kennytm

已经解决了。请再次确认（我是边做边想的）。 - polygenelubricants

我不确定你的复杂度估计是否准确。如果顶点的入度>1，那么对getCount()的递归调用是否意味着这些顶点可能会被访问多次呢？ - ChrisH

已经解决了。请再次确认（我是边做边想的）。 - polygenelubricants

啊，是的，我忽略了记忆化。 - ChrisH

这个算法是不正确的。在一张钻石图上 A -> B，A -> C，B -> D，C -> D，它返回 getCount(A)=4，然而正确答案是3。 - jkff

Answer 5

我假设你有一个包含所有顶点的列表，每个顶点都有一个id和一个可以直接到达它的顶点列表。

然后，你可以添加另一个字段（或者你如何表示它），用于保存你也可以间接到达的顶点。我会使用递归深度优先搜索来完成这个过程，并将结果存储在相应到达节点的字段中。作为这个过程的数据结构，你可能会使用一些允许有效去重的树形结构。

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

- Svante

---

那是我的第一个实现。这种技术有效，但它构建了基础DAG的完整传递闭包。 - ChrisH

好的，你需要一些方法来消除重复。 - Svante

是的，但可能不需要一次性存储完整的闭包。我认为在构建整个闭包之前，可以先获取某些顶点的答案，并在遍历完成的顶点中丢弃可达性。 - ChrisH