查找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群体可以提出什么。

---

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

为了找到不可达性，在相反的方向再次进行。

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

---

OMG是错误的！ 抱歉！

我会留下来，直到有一个好的选择。 如果可能的话，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] 。

另一种看待它的方法是计算每个边沿将被跟随的次数：恰好一次。

---

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

在[0，1）范围内为每个顶点分配一个随机数。 使用线性时间动态程序（如polygenelubricants's）为每个顶点v计算从v到达的最小数目minreach（v）。然后估计从v到达的顶点数为1 / minreach（v）-1。为了获得更好的精度，几次，并在每个顶点取平均值。

链接地址: http://www.djcxy.com/p/45145.html

上一篇: Finding the Reachability Count for all vertices of a DAG

下一篇: What are good jQuery plugins to highlight code and XML content?