如何计算有向图中的所有可达节点？ [英] How to count all reachable nodes in a directed graph?

问题描述

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

There is a directed graph (which might contain cycles), and each node has a value on it, how could we get the sum of reachable value for each node. For example, in the following graph:

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

the reachable sum for node 1 is: 2 + 3 + 4 + 5 + 6 + 7 = 27

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

the reachable sum for node 2 is: 4 + 5 + 6 + 7 = 22

.....

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

My solution: To get the sum for all nodes, I think the time complexity is O(n + m), the n is the number of nodes, and m stands for the number of edges. DFS should be used,for each node we should use a method recursively to find its sub node, and save the sum of sub node when finishing the calculation for it, so that in the future we don't need to calculate it again. A set is needed to be created for each node to avoid endless calculation caused by loop.

可以吗？我认为它不够优雅，尤其是必须创建许多场景。有更好的解决方案吗？谢谢。

Does it work? I don't think it is elegant enough, especially many sets have to be created. Is there any better solution? Thanks.

推荐答案

可以先找到牢固连接的组件（SCC），可以在 O（| V | + | E |）。然后，为SCC（每个SCC是图中的一个节点）建立一个新的图形 G'，其中每个节点的值都是该节点的和。

This can be done by first finding Strongly Connected Components (SCC), which can be done in O(|V|+|E|). Then, build a new graph, G', for the SCCs (each SCC is a node in the graph), where each node has value which is the sum of the nodes in that 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，问题变得更加简单，并且似乎是在评论中链接的问题的变体。

Then, this graph (G') is a DAG, and the question becomes simpler, and seems to be a variant of question linked in comments.

编辑从此刻开始，以前的答案（被删除）是一个错误，请使用新的答案进行编辑。抱歉。

EDIT previous answer (striked out) is a mistake from this point, editing with a new answer. Sorry about that.

现在，可以从每个节点使用DFS查找值的总和：

Now, a DFS can be used from each node to find the sum of values:

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，因为不必担心会重复计算两次



针对此问题的DP解决方案（DAG）可以是：

A DP solution for this problem (DAG) can be:

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

这可以在线性时间（在DAG的拓扑排序。

This can be calculated in linear time (after topological sort of the DAG).

伪代码：



1. 查找SCC


2. 构建G'


3. 拓扑排序G'


4. 查找G'中每个节点的D [i]


5. 对U_i中的所有节点u_i应用值，对于每个U_i。


1. Find SCCs
2. Build G'
3. Topological sort G'
4. Find D[i] for each node in G'
5. apply value for all node u_i in U_i, for each U_i.

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

Total time is O(|V|+|E|).

这篇关于如何计算有向图中的所有可达节点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！