如何找到從某個頂點到達的所有邊的總和？

Question

考慮一個沒有周期的有向圖。我需要爲每個u找到從u到達的邊的總權重（通過可達我們的意思是有從u到一些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

您可以使用自下而上的方法。即首先計算每個頂點的outdegree，現在0 outdegree的頂點對它們的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); 
} 
}