有向无环图中所有节点的可达性计数

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中解决这个问题，但我认为这是可能的。比赛结束后，我用下面的代码成功通过了24个测试用例中的13个：

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 的输入，它可能是具有大量节点和边（即 50，000 个节点和 40，000 个边）的输入，它都会失败。由于无法识别或构思出更快，更节省内存的算法，我对下一步该尝试完全不知所措。考虑过使DFS迭代，但我认为记忆数千个数组的内存消耗将使之相形见绌，这似乎是主要问题。我在Hackerrank上收到“中止调用”和“运行时错误”，用于失败的11个测试（与“超时”相反）。还尝试了带有“联合”的“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。

首先，我必须道歉，但我的JavaScript技能不是很好（即它们不存在），所以我下面的解决方案使用Java，但这些想法应该很容易移植。

您最初的问题遗漏了一个非常重要的细节：我们只需要找到可到达节点数大于或等于|V|/2的所有节点

这有什么关系？计算每个节点的可达节点的数量是昂贵的，因为我们必须从图中的每个节点开始进行DFS或BFS。但是如果我们只需要找到具有上述属性的节点，那就容易多了。

假设后继者(n)是从n可到达的所有节点，祖先(n)是可到达n的所有节点。我们可以使用以下观察结果来大大减少搜索空间:

< li >如果从n可到达的节点数小于|V| / 2，则后继(n)中的节点数不能大于n < li >如果从n可到达的节点数大于或等于|V| / 2，则祖先(n)中的所有节点将具有更大的数目

我们如何利用这一点？

1. 创建图形时，还要创建转置的图形。这意味着在存储边缘时

使用迭代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，但使用转置图。请注意，我们可以重用访问的数组，因为我们将使用的所有值都是假的，因为这是一个非循环图。

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;
}

标记继任者的功能

请注意，我们已经有了后继节点，因为它们只是我们将＜code＞visited＜/code＞设置为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秒。如果你颠倒迭代顺序(例如，在< code>solve中，你从最大的节点id开始),它会下降到4秒，但这有点像欺骗^^