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

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，问题就简单了，好像是的变体。

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之后）。

伪代码：

查找 SCC

构建 G'

拓扑排序G'

为G'中的每个节点求D[i]

为 U_i 中的所有节点 u_i 应用值，为每个 U_i.

~~总时间是 O(|V|+|E|).~~

Answer 2

您可以使用 DFS or BFS 算法来解决您的问题。两者都有复杂性 O(V + E)

您不必计算所有节点的所有值。而且你不需要递归。就做这样的事情。

典型的 DFS 看起来像这样。

unmark all vertices
choose some starting vertex x
mark x
list L = x
while L nonempty
    choose some vertex v from front of list
    visit v
    for each unmarked neighbor w
        mark w
        add it to end of list

在你的情况下你必须添加一些行

unmark all vertices
choose some starting vertex x
mark x
list L = x
float sum = 0
while L nonempty
    choose some vertex v from front of list
    visit v
    sum += v->value
    for each unmarked neighbor w
        mark w
        add it to end of list

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

How to count all reachable nodes in a directed graph?

algorithm

graph

directed-graph