用於在向非循環圖的從每個頂點不同的路徑數線性時間算法

我關於一個算法模塊以下過去紙問題工作：用於在向非循環圖的從每個頂點不同的路徑數線性時間算法

設G =（V，E）是一個簡單的引導無環圖（DAG）。
對於V中的一對頂點v，u，我們說如果在G中存在從u到v的（有向）路徑，則v可以從u到達。
（我們假設每個頂點都可以從它自己到達）
對於V中的任何頂點v，令R（v）爲頂點v的可達性數，它是從V到達的V中的頂點u的數目。
設計算法，對於給定的DAG，G = （V，E）計算V中所有頂點v的R（v）值。
提供您的算法的分析（即正確性和運行時間分析）。
（理想情況下，應儘量設計一個算法在 Ø上運行（N + M）的時間。）

所以，到目前爲止，我有以下想法：

以下算法查找拓撲排序的DAG中可能是有用的：

TopologicalSort(G) 
    1. Run DFS on G and compute a DFS-numbering, N // A DFS-numbering is a numbering (starting from 1) of the vertices of G, representing the point at which the DFS-call on a given vertex v finishes. 
    2. Let the topological sort be the function a(v) = n - N[v] + 1 // n is the number of nodes in G and N[v] is the DFS-number of v.

我的第二個想法是，動態規劃可能是一個有用的方法，太。
但是，我目前不確定如何將這兩個想法合併到一個解決方案中。

我將不勝感激提示！

來源

2016-05-23 CKKOY

編輯：不幸的是，下面的方法一般不正確。它可能會多次計算可以通過多個路徑到達的節點。

如果DAG是polytree，那麼下面的想法是有效的，因爲這保證了任何兩個節點之間至多有一條路徑。

可以使用以下步驟：

找到的所有節點與度0（即沒有傳入邊緣）。

這可以在O(n + m),例如，通過循環遍歷所有邊緣並標記那些結束任何邊緣的節點。具有0度的度數的節點是未被標記的節點。

從0 in度的每個節點開始DFS。

在節點的DFS調用結束後，我們希望爲該節點計算其可達性信息。

爲了達到這個目的，我們需要添加這個節點的後繼的可達性。其中一些值可能已經計算得出（如果DFS已經訪問過後繼者），因此這個是一個動態編程解決方案。

下面的僞代碼描述了DFS代碼：
function DFS(node) { 
    visited[node] = true; 
    reachability[node] = 1; 

    for each successor of node { 
     if (!visited[successor]) { 
      DFS(successor); 
     } 
     reachability[node] += reachability[successor]; 
    } 
} 
調用此用於與度0的所有節點之後，reachability 陣列將包含可達性圖中的所有節點。

整體複雜度爲O(n + m)。

來源

2016-05-23 12:25:40 qwertyman

這些步驟很有用;不過，我認爲DFS的僞代碼可能存在錯誤。我已將它應用於我繪製的任意DAG，並且所有可訪問性條目保持爲0. – CKKOY

的確，可達性應該已在DFS中初始化爲1（每個節點都可以到達自己） - 現在進行編輯。還有另一個問題使算法無效（某些節點可能會被多次計數）。我正在考慮處理這個問題的方法。 – qwertyman

我建議使用廣度優先搜索方法。

對於每個節點，添加連接到隊列的所有節點。除此之外，維護一個單獨的數組來計算可達性。

例如，如果一個A-> B，則

1.) Mark A as traversed 
2.) B is added to the queue 
3.) arr[B]+=1

通過這種方式，我們可以得到R（v）中爲O所有頂點（| V | + | E |）通過ARR [時間]。

來源

2016-05-23 13:35:45 attaboy182

用於在向非循環圖的從每個頂點不同的路徑數線性時間算法

回答

相關問題