algorithm - 如何计算有向图中所有可达节点？

Question

有一个有向图(可能包含环)，每个节点都有一个值，我们如何得到每个节点可达值的总和。例如，在下图中:

节点 1 的可达和是:2 + 3 + 4 + 5 + 6 + 7 = 27

节点 2 的可达和是:4 + 5 + 6 + 7 = 22

.....

我的解决方案:求所有节点的总和，我认为时间复杂度是O(n + m)，n是节点数，m是边数。应该使用DFS，对于每个节点我们应该用一种方法递归的找到它的子节点，计算完后把子节点的和保存起来，这样以后就不用再计算了。需要为每个节点创建一个集合，避免循环造成的无休止计算。

有用吗？我觉得不够优雅，尤其是要创建很多set。有没有更好的解决办法？谢谢。

Answer 1

这可以通过首先找到 Strongly Connected Components (SCC) 来完成，这可以在 O(|V|+|E|) 中完成。然后，为 SCC(每个 SCC 是图中的一个节点)构建一个新图 G'，其中每个节点的值是该 SCC 中节点的总和。

正式地，

G' = (V',E')
Where V' = {U1, U2, ..., Uk | U_i is a SCC of the graph G}
E' = {(U_i,U_j) | there is node u_i in U_i and u_j in U_j such that (u_i,u_j) is in E }

那么，这个图(G')就是一个DAG，问题就变简单了，好像是question linked in comments的一个变体.

EDIT 以前的答案(划线)从这一点来看是错误的，用新答案进行编辑。对此感到抱歉。

现在，可以从每个节点使用 DFS 来查找值的总和:

DFS(v):
  if v.visited:
    return 0
  if v is leaf:
    return v.value
  v.visited = true
  return sum([DFS(u) for u in v.children])

• 这是 O(V^2 + VE) 最差的花瓶，但是由于图的节点较少，V和 E 现在显着降低。
• 可以做一些局部优化，例如，如果一个节点只有一个 child ，你可以重复使用预先计算的值，而不是再次对 child 应用 DFS，因为在这种情况下不用担心计数两次。

这个问题的DP解法(DAG)可以是:

D[i] = value(i) + sum {D[j] | (i,j) is an edge in G' }

这可以用线性时间计算(在 DAG 的 topological sort 之后)。

伪代码:

1. 查找 SCC
2. 构建 G'
3. 拓扑排序G'
4. 为G'中的每个节点找到D[i]
5. 为U_i中的所有节点u_i应用值，对于每个U_i。

总时间是 O(|V|+|E|)。