javascript - 有向无环图中所有 Node 的可达性计数

Question

因此，Hackerrank 上的一项名为“无环图”的编程竞赛提出了这个挑战，它基本上归结为计算从“有向无环图”中的每个 Node 可到达的 Node 数。例如，假设您有这样的图表:

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

可达性计数(包括源 Node ):

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

我的方法是使用内存的“深度优先”遍历。环顾四周，但由于在这种情况下发生的过度计数，运行时间似乎无法进一步改进:

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

第三个 Node 将计算第四个 Node ，即使第二个 Node 已经计算了第四个 Node 。更糟糕的是，我只用 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 的输入，它都失败了，可能是具有大量 Node 和边的输入(即 50,000 个 Node 和 40,000 个边)。由于未能确定或构思出一种更快、内存效率更高的算法，我完全不知道接下来要尝试什么。考虑过使 DFS 迭代，但我认为内存数千个数组的内存消耗将使它相形见绌，这似乎是主要问题。对于失败的 11 个测试(与“超时”相对)，我在 Hackerrank 上收到“Abort Called”和“Runtime Error”。还尝试了“bitSets”和“union”，但内存消耗变得更糟，因为 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 但这些想法应该很容易移植。

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

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

设 successors(n) 是从 n 可达的所有 Node ，ancestor(n) 是可以到达 n 的所有 Node 。我们可以使用以下观察结果来大幅减少搜索空间:

• 如果 n 可达的 Node 数小于 |V|/2 那么successors(n) 中的 Node 都不能有更大的数
• 如果从 n 可达的 Node 数大于或等于 |V|/2 那么ancestors(n)中的所有 Node 都会有一个更大的数

我们如何使用它？

1. 创建图形时，还要创建转置图形。这意味着当存储边 a->b 时，您将 b->a 存储在转置图中。
2. 创建一个数组来存储要忽略的 Node ，用false初始化它
3. 实现一个基于 DFS 的函数，确定给定 Node 是否有多个可达 Node >= |V|/2(见下文)
4. 在该函数中，忽略标记为已忽略的 Node
5. 如果 Node n的 Node 数小于|V|/2，将successors(n)中的所有 Node 标记为忽略
6. 否则计算ancestors(n)中的所有 Node 并将它们标记为忽略

使用迭代 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 的 Node 。

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 中你从最大的 Node id 开始)它会下降到 4 秒，但这有点像作弊 ^^