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

Question

有一个有向图（可能包含环），每个节点上都有一个值，我们如何得到每个节点可达值的总和。例如，在以下图中：

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

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

.....

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

这个方案可行吗？我认为它还不够优雅，尤其是需要创建许多集合。有更好的解决方案吗？谢谢。

- user8142520

---

可能是有向无环图中所有节点可达性计数的重复问题。 - Prune

谢谢@Prune，但我说的是有向图而不是DAG。 - user8142520

在这种情况下，算法非常相似；您只需保留已访问节点的列表，以过滤添加到“未完成”列表中的内容。 - Prune

Answer 1

这可以通过首先查找强连通分量（SCC）来完成，可以在O（|V| + |E|）的时间内完成。然后，为SCC构建一个新图G'（每个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，问题变得更简单，似乎是评论中提到的问题的一种变体。 编辑之前的答案（已删除线）是从此处开始的错误，现在用新答案进行编辑。对此感到抱歉。

现在可以从每个节点使用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现在显著降低。
• 可以进行一些局部优化，例如，如果一个节点只有一个子节点，则可以重复使用预计算值，并且不再对该子节点应用DFS，因为在这种情况下不会出现重复计数的情况。

该问题（DAG）的DP解决方案如下：

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应用值。

总时间复杂度为O（|V| + |E|）。

- amit

---

这个DP解法会不会重复计算具有多条路径的节点？ - luqui

这个和图的传递闭包有什么区别吗？据我所知，这是无法在此时间内计算出来的，但是就我而言，我就是想不明白这个有什么，而这个没有。 - user2268997

@luqui 是的，你说得对。在这种情况下，这些节点将被计算两次。 - Moustafa Saleh

感谢您的评论。我不知道如何修复它，所以它被忽略了。这里有一个小修复。比我希望的要少得多。我仍然希望有一种方法可以重复使用预先计算的数据，但目前还不确定如何做到。我仍然认为在此之前使用SCC可能是一个好主意。由于SCC是线性的，只需保存恒定数量的节点即可，在运行四次跟进算法时将会得到回报。 - amit

Answer 2

你可以使用深度优先搜索或广度优先搜索算法来解决你的问题。 两者的时间复杂度都是O(V + E)。

你不需要为所有节点计算所有值，也不需要递归。 只需按以下方式进行操作即可。

通常深度优先搜索的代码如下。

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

- Gor

---

请注意，此解决方案对于单个节点的时间复杂度为 O(|V|+|E|)。如果您想要找到从每个顶点可达的所有节点的总和，则需要再次对每个节点运行该算法，总时间复杂度为 O(|V|^2 + |E||V|)（这也是问题所要求的）。 - amit