如何找到从某个顶点可达的所有边的总权重？

Question

Consider a directed graph with no cycles. I need to find for each u the total weight of edges reachable from u (by reachable we mean there's a path from u to some v).

现在，我想到的是运行宁拓扑排序然后开始运行从最后一个节点到第一个节点（可以通过互换边的方向）

然后我们正在评估 f[v] = f[u] + w(u,v)。

但是有一个问题；对于此图，我们将计算 f[d] 两次。我怎样才能克服这个？

Answer 1

您可以使用 BFS 或 DFS 来实现。

total = 0
dfs (node):
  if visited[node] == 1:
      return
  visited[node] = 1
  for all u connected to node:
      total += weight[node][u]
      dfs(u)

注意我们检查了total += weight[node][u]之后的访问。

Answer 2

您可以使用自下而上的方法。即首先计算每个顶点的出度，现在出度为 0 的顶点的 F[u] = 0。现在将所有此类顶点添加到队列 Q.
您还需要存储图形的转置，假设它是 T.

While(!Q.empty){
u=Q.front();
Q.pop();
for all edges E originating from T[u]{
F[v]+=w; (where (u,v) was the edge with w as weight)
//now remove u from the graph
outdegree[v]--;
if(outdegree[v]==0)
Q.push(v);
}
}

如何找到从某个顶点可达的所有边的总权重？

How to find the sum weight of all edges reachable from some vertex?

algorithm

computer-science

graph