可達性計數在向非循環圖的所有節點

Question

因此就出現了對Hackerrank編程大賽這一挑戰被稱爲「無環圖」，這基本上可以歸結爲一個「向非循環圖計算節點的每個節點可到達的數」。例如，假設你有一個圖表，像這樣：

[ 1 ] ---->[ 2 ]--->[ 4 ]--->[ 5 ] 
[ 3 ] ------/ 

可達數（包括原始節點）：

Node 1: 4 
Node 2: 3 
Node 3: 4 
Node 4: 2 
Node 5: 1 

我的做法是一個「深度優先」的穿越與記憶化。環顧四周相當多，但它好像在運行時無法得到更進一步，因爲發生的情況下，像這樣的過度計數的改進：

[ 1 ] ---->[ 2 ]--->[ 4 ]--->[ 5 ] 
[ 3 ] ------/--------/ 

第三個節點將計算第四節點，甚至儘管第二個節點已經計入第四個節點。爲了讓事情變得更糟，我只用JavaScript解決了這些挑戰。它是我的主要語言，我從推動其界限中獲得快感。領導委員會中沒有人用JavaScript解決它，但我認爲這是可能的。比賽結束後，我設法通過13的24個測試案例用下面的代碼：

function Solution(graph, nodes) { 

    var memory = new Array(nodes + 1) 
     , result = 0; 

    graph.forEach((a, v) => DepthFirstSearch(graph, v, memory)); 

    // challenge asks for an output variation, but the accurate 
    // reachability count of every node will be contained in "d.length". 
    memory.forEach((d, i) => { if (i && (2 * d.length) >= nodes) result++; }); 

    return result; 
} 

function DepthFirstSearch(graph, v, memory) { 

    if (memory[ v ]) return memory[ v ]; 

    var descendants = new Uint16Array([ v ]); 

    graph[ v ].forEach(u => { 

     descendants = MergeTypedArrays( 
      DepthFirstSearch(graph, u, memory), 
      descendants 
     ); 
    }); 
              // make elements unique 
              // to avoid over counting 
    return memory[ v ] = Uint16Array.from(new Set(descendants)); 
} 

function MergeTypedArrays(a, b) { 

    var c = new a.constructor(a.length + b.length); 

    c.set(a); 
    c.set(b, a.length); 

    return c; 
} 

// adjacency list 
var graph = [ 
    [], // 0 
    [ 2 ], // 1 
    [ 4 ], // 2 
    [ 2 ], // 3 
    [ 5 ], // 4 
    []  // 5 
]; 

var nodes = 5; 

Solution(graph, nodes); 

它未能超過50KB更大的所有投入，以大組節點和邊緣（即5萬個節點和大概投入40,000條邊）。無法識別或設想更快，更高效的內存算法，我完全喪失了接下來要嘗試的內容。思考如何使DFS迭代，但我認爲記憶數千個數組的內存消耗會使這個問題變得更加嚴重，這似乎是主要問題。我在Hackerrank上獲得了11次失敗的測試（與「超時」相反）的「Abort Called」和「Runtime Error」。還嘗試過使用「union」的「bitSets」，但由於bitSets數組需要足夠大以存儲高達50,000的數字，所以內存消耗變得更糟。

約束：

1 ≤ n,m ≤ 5×10^4 
1 ≤ a(i),b(i) ≤ n and a(i) ≠ b(i) 
It is guaranteed that graph G does not contain cycles. 

只想說清楚，我不會得到任何分通過了所有的測試，因爲這個挑戰被鎖定，這是教育的目的，主要是優化。我意識到相關的SO帖子指向拓撲排序，但據我所知，拓撲排序仍然會超過上述情況，因此不是一個可行的解決方案。如果我誤解了，請賜教。預先感謝您的時間。

問：如何優化這進一步？有沒有更高效的方法？

Answer 1

深度優先搜索（DFS）是解決這一問題的一個好辦法。另一種方式是廣度優先搜索（BFS），它也可以並行運行，並且可以很好地進行優化 - 但所有代價都高於代碼複雜度。所以我的建議是堅持DFS。

首先我必須apoligize，但我的JavaScript技能不是很好（即它們是不存在的），所以我下面的解決方案是使用Java，但思路應該很容易端口。

您最初的問題是缺少一個非常重要的細節：我們只需要找到的所有節點，其中到達節點的數量比|V|/2

大於或等於爲什麼是怎麼回事？計算每個節點的可達節點數量非常昂貴，因爲我們必須從圖中的每個節點開始執行DFS或BFS。但是如果我們只需要找到具有上述屬性的節點，那就容易多了。

讓接班人（N）從ñ和祖先（N）是可以達到ň所有節點可到達的所有節點。 我們可以使用下面的觀測drasticly減少搜索空間：

• 如果節點從ñ可達數大於小| V |/2然後在繼任沒有節點（n）的可具有較大數目
• 如果節點從Ñ可達數爲大於或小於等於| V |/2然後在祖先（n）的所有節點將有較大數量的

我們如何使用？

1. 創建圖形時，還要創建轉置圖形。這意味着當存儲邊a-> b時，您將b-> a存儲在轉置圖中。
2. 創建一個陣列哪些節點忽略存儲與false
3. 初始化它實現一個DFS基於函數，確定給定節點是否具有數可達節點>= |V|/2的（見下文）
4. 在該功能，忽視標記爲忽略的節點
5. 如果對於節點n節點數小於| V |/2，標誌着繼任（n）的作爲忽略
6. 否則計數的所有節點在祖先（n）的並將其標記爲使用迭代DFS
   忽略

解決方案的所有節點

public int countReachable(int root, boolean[] visited, boolean[] ignored, Graph graph) { if (ignored[root]) { return 0; } Stack<Integer> stack = new Stack<>(); stack.push(root); int count = 0; while (stack.empty() == false) { int node = stack.pop(); if (visited[node] == false) { count++; visited[node] = true; for (int neighbor : graph.getNeighbors(node)) { if (visited[neighbor] == false) { stack.push(neighbor); } } } } if (count * 2 >= graph.numNodes()) { return markAndCountAncestors(root, visited, ignored, graph); } else { return markSuccessors(root, visited, ignored, graph); } } 

功能，以紀念祖先

這只是另一個DFS，但使用轉置圖。請注意，我們可以重複使用visited陣列，因爲我們將使用的所有值都是false，因爲這是一個非循環圖。

public int markAndCountAncestors(int root, boolean[] visited, boolean[] ignored, Graph graph) { 
    Stack<Integer> stack = new Stack<>(); 
    stack.push(root); 
    visited[root] = false; 

    int count = 0; 
    while (stack.empty() == false) { 
     int node = stack.pop(); 
     if (visited[node] == false && ignored[node] == false) { 
      count++; 
      visited[node] = true; 
      ignored[node] = true; 
      for (int neighbor : graph.transposed.getNeighbors(node)) { 
       if (visited[neighbor] == false && ignored[node] == false) { 
        stack.push(neighbor); 
       } 
      } 
     } 
    } 
    return count; 
} 

功能，以紀念繼任

請注意，我們已經擁有了繼任者，因爲他們只是在這裏我們設置visited爲true的節點。

public int markSuccessors(int root, boolean[] visited, boolean[] ignored, Graph graph) { 
    for(int node = 0; node < graph.numNodes(); node++) { 
     if (visited[node)) { 
      ignored[node] = true; 
     } 
    } 
    return 0; 
} 

函數來計算結果

public void solve(Graph graph) { 
    int count = 0; 
    boolean[] visited = new boolean[graph.numNodes()]; 
    boolean[] ignored = new boolean[graph.numNodes()]; 
    for (int node = 0; node < graph.numNodes(); node++) { 
     Arrays.fill(visited, false); // reset visited array 
     count += countReachable(node, visited, ignored, graph); 
    } 
    System.out.println("Result: " + count); 
} 

在您發佈的大型測試的情況下，這將運行7.5秒對我來說。如果您反轉迭代順序（即在solve中以最大節點ID開頭），它會降低到4秒，但這有點像作弊^^