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

Question

有一个有向图(可能包含循环),每个节点都有一个值,我们怎么能得到每个节点的可达值之和.例如,在下图中:

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

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

.....

我的解决方案:为了获得所有节点的总和,我认为时间复杂度为O(n + m),n是节点数,m代表边数.应该使用DFS,对于每个节点,我们应该递归地使用一个方法来找到它的子节点,并在完成它的计算时保存子节点的总和,以便将来我们不需要再次计算它.需要为每个节点创建一个集合,以避免由循环引起的无限计算.

它有用吗？我认为它不够优雅,特别是必须创建许多套装.有没有更好的解决方案？谢谢.

Answer 1

这可以通过首先找到可以在其中完成的强连接组件(SCC)来完成O(|V|+|E|).然后,G'为SCC 构建新图(每个SCC是图中的节点),其中每个节点具有值,该值是该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,问题变得更简单,似乎是评论中链接的问题的变体.

针对此问题的DP解决方案(DAG)可以是:

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

这可以在线性时间内计算(在DAG的拓扑排序之后).

伪代码:

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

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