DAG中兩個節點之間的路徑數

Question

我想要查找DAG中兩個節點之間的路徑數。 O（V^2）和O（V + E）是可接受的。 O（V + E）提醒我以某種方式使用BFS或DFS，但我不知道如何使用BFS或DFS，但我不知道如何使用BFS或DFS。 有人可以幫忙嗎？

Answer 1

做一個拓撲排序的DAG，然後將目標的頂點向後掃描到源。對於每個頂點v，保留從v到目標的路徑數量。當你到達源頭時，計數值就是答案。那是O(V+E)。

Answer 2

從節點u到v的不同路徑的數量是從節點x到v的不同路徑的總和，其中x是u的直接後裔。

存儲每個節點（臨時設置爲0）的目標節點v的路徑數量，使用相反方向從v（此處值爲1）開始，併爲每個節點重新計算此值（將所有子節點的值）直到你到達你。

如果按拓撲順序處理節點（又是相反的方向），則可以保證在訪問給定節點時已經計算了所有直接後代。

希望它有幫助。