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

http://www.guardian.co.uk/world/2006/jul/20/secondworldwar.tvandradio

在[0,1]范围内为每个顶点指定一个随机数。使用一个线性时间动态程序,如polygene的,来计算每个顶点v的最小可达数(v)。然后估计从v到达的顶点数为1/minreach(v)-1。为了获得更好的精度,重复几次,并在每个顶点取平均值的中位数。

在相反的方向上再做一次,以找到可达性中的。

时间复杂度:O(MN+N) ^2. ),空间复杂度:O(M+N)。

我为这个问题想出了一个可行的解决办法。我的解决方案基于对 topological sorting 算法。下面的算法只计算传递闭包中的in度。输出度可以用同样的方式计算,边反转,每个顶点的两个计数相加,以确定最终的“可达性计数”。

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

假设set操作是O(1),这个算法在O(| V |+| E |)中运行。但是,更可能的情况是,set union操作 predecessors[V2].add(predecessors[V])

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

使用动态规划。

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) .

我假设你有一个所有顶点的列表,每个顶点都有一个 id 以及可以直接从中访问的顶点列表。

然后,您可以添加另一个字段(或以您表示的方式),该字段包含您也可以间接到达的顶点。我将在递归的深度优先搜索中这样做,将结果存储在相应到达节点的字段中。作为这种情况的数据结构,您可能会使用某种允许有效删除重复项的树。