在一个图中，如何高效地计算一个节点可以到达的所有节点的总和？

Question

在一个图中，如何高效地计算一个节点可以到达的所有节点的总和？

algorithmgraph

7

给定一张有向图，每个节点都有一个权重。从任意节点A开始，存在一组可以到达的节点。定义SUM为这个集合的总权重。

问题：如何高效地计算该图中每个节点的SUM？该图可能包含数百万个节点。

更新1：图数据结构由起始节点集合组成，每个节点都有一个指向其他节点的集合。

我尝试过：递归计算每个节点的后代，并根据后代集合计算SUM。但是这种递归非常低效，因为我必须进行大量的集合并、迭代操作。此外，我尝试在每个节点缓存后代集合。然而，它很容易耗尽内存。

更新2：示例图，边都是有向的，上层节点指向下层节点。 Sample Graph

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

- Yan Li

所以对于给定的节点，其总和是包含该节点的所有连通分量中的所有节点的权重之和？ - Dan D.

@Dan D. 是的，抱歉我没有及时注意到你的回复... - Yan Li

是否有其他的假设？例如，点到节点集合的大小为O(1)？ - Matthijs Wessels

另外，您希望这个算法如何高效？您提到了内存。也许您想优化缓存未命中而不仅仅是运行时间？ - Matthijs Wessels

@Matthijs Wessels，关于图形没有其他假设。实际上，我期望有一个比我的递归解决方案复杂度更低的算法。 - Yan Li

2个回答

0

我的先前答案是一个好主意，但包含交叉子树的排除非常难以解决（我认为您的递归方法也会受到影响）。想一想，我开始怀疑在这个问题中是否存在最优子结构，可以借助动态规划解决...

我将提出一个更简单（尽管不太高效）的解决方案：

对于每个节点，运行BFS / DFS并总结所有遇到的节点的值。它将在O（V）空间和O（V（E + V））= O（EV）时间内运行，但实现起来非常简单，不需要递归。

您可以通过找到SCC图表并在每个SCC上执行BFS / DFS而进行优化。如果图形“团体”，则这可能会使运行时间增加很多。

- davin

我担心图中没有太多的强连通分量。我仍在尝试找到一种不需要在那么多节点上执行BFS/DFS的方法。对于我需要处理的真实图形，E和V都高达100万，O(EV)是不可接受的。无论如何，还是非常感谢你们 :) - Yan Li

幸运的是，这个程序可以在多核服务器上分发。而且现在运行时间也是可以接受的。 - Yan Li

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- davin · Accepted Answer

使用Tarjan算法或双重DFS运行查找图的强连通分量。

对于每个强连通分量，计算其中所有节点权重的总和，并将此值表示为PARTIAL-SUM。

按照反向拓扑顺序迭代强连通分量；对于每个强连通分量中的每个节点，其SUM将是相邻强连通分量的所有SUM值以及其自身PARTIAL-SUM值的总和。

线性运行时间O(E+V)，因为查找强连通分量是线性的，拓扑排序是线性的，并且由于我们最多访问每个强连通分量一次和每个分支一次，所以求和也是线性的。

编辑

如tzkuzzy在评论中指出的，平行路径会带来问题。这可以通过在强连通分量图上运行简单的DFS来解决。在任何交叉边上，我们只需沿着DFS树向上取已经访问过的节点，直到达到未完全搜索的父节点，这对节点（底部的已访问节点和祖先）之间有两条不同的路径，我们为每个节点列出这样的后代列表，在求和时仅需减去它们的PARTIAL-SUM值。

因此，如果：

 u
/ \
\ /
 w

我们的深度优先搜索会选择从节点 u 的子节点连接到 w 的交叉边，并追溯回到 u（对于熟悉学校里典型 DFS 的人来说，最简单的解释是将 u 视为 w 的第一个灰色祖先），因此我们将 w 添加到我们在 u 上维护的列表中。

然后，当我们像描述的那样对每个 SCC 的相邻 SCC 进行求和时，我们添加了一个额外的步骤，在其中循环遍历提到的列表并简单地减去部分和值。

DFS 本身仍然是线性的。如果我们缓存结果（这样我们不会多次遍历同一条边），则从节点回溯到祖先可能是线性的。而求和中的额外工作最多为 O(V)，因此我们没有改变运行时间。

编辑：

容斥使这比我最初想象的更加困难。这个解决方案不完整也不起作用。对于每个节点进行简单 BFS 更昂贵但更容易，并且将有效工作。