在图中,如何计算节点可以有效达到的所有节点的总和？

Question

给定有向图,将权重分配给每个节点.
从任何节点A开始,将有一组可以从A到达的节点.
将SUM定义为该集合的总权重.

问题:如何有效地计算此图中每个节点的SUM？
该图可能包含数百万个节点.

更新1:
图形数据结构由一组起始节点组成,每个节点都有一组指向节点.

我尝试过:
递归计算每个节点的后代,并根据后代集计算SUM.这种递归效率非常低,因为我必须多次设置union,uteration操作.此外,我试图在每个节点缓存后代集.但是,它很容易耗尽内存.
那么,还有其他解决方案吗？

更新2:
示例图,边缘全部是定向的,上部节点指向较低的节点

结果应为
SUM(1)= 55 SUM(2)= 35 SUM(3)= 41 SUM(4)= 19 SUM(5)= 22 SUM(6)= 25 ......

Answer 1

找到图表的SCC(Tarjan的算法,或双DFS运行).

对于每个SCC计算它的节点权重之和,用PARTIAL-SUM表示该值.

以反向拓扑顺序迭代SCC; 对于每个SCC中的每个节点,其SUM将是相邻SCC的所有SUM值加上它自己的PARTIAL-SUM值的总和.

O(E+V)自发现SCC以来的线性运行时间是线性的,拓扑排序是线性的,并且求和是线性的,因为我们最多访问每个SCC一次并且每个分支最多访问一次.

编辑

正如在tzkuzzy并行路径的评论中指出的那样构成一个问题.通过SCC图上的简单DFS运行可以轻松解决这个问题.在任何跨边缘上,我们只需将已访问过的节点放在DFS树上,直到我们到达未完全搜索的父节点,这对节点(底部访问的节点和祖先)之间有两条不同的路径,我们为这些后代的每个节点创建一个列表,并且总和只是减去它们的PARTIAL-SUM值.

因此,如果:

 u
/ \
\ /
 w

我们的DFS会拿起从子节点连接的交叉边缘u到w,并追溯u(对于那些熟悉学校任教典型的DFS最简单的解释是,u被定性为第一灰色的祖先w),所以我们添加w到我们维护的清单u.

然后,当我们按照描述对每个SCC的相邻SCC求和时,我们添加一个额外的步骤,我们遍历所提到的列表并简单地减去PARTIAL-SUM值.

DFS本身仍然是线性的.如果我们缓存结果,那么从节点到祖先的回溯可以是线性的(这样我们不会多次遍历同一个边缘).总和中的额外工作最多O(V),所以我们没有改变运行时间.

编辑

包含 - 排除使得这比我最初的想法更难.此解决方案不完整,不起作用.每个节点的简单BFS更昂贵但更容易并且可以工作.