Счетчик достижимости для всех узлов в направленном ациклическом графе

Поиск в глубину (DFS) — один из хороших способов решения этой проблемы. Другим способом может быть поиск в ширину (BFS), который также может работать параллельно и может быть очень хорошо оптимизирован, но все это за счет гораздо более высокой сложности кода. Поэтому я бы рекомендовал придерживаться DFS.

Во-первых, я должен извиниться, но мои навыки JavaScript не очень хороши (т. е. их не существует), поэтому мои решения ниже используют Java, но идеи должны быть легко переносимы.

В вашем первоначальном вопросе отсутствует одна очень важная деталь: нам нужно только найти все узлы, где количество достижимых узлов больше или равно |V| / 2

Почему это имеет значение? Вычисление количества достижимых узлов для каждого узла требует больших затрат, поскольку мы должны выполнять DFS или BFS, начиная с каждого узла в графе. Но если нам нужно найти только узлы с вышеуказанным свойством, это намного проще.

Пусть successors(n) — все узлы, достижимые из n, а ancestor(n) — все узлы, которые могут достигать n. Мы можем использовать следующие наблюдения, чтобы резко сократить пространство поиска:

• если количество узлов, достижимых из n, меньше, чем |V| / 2, то ни один узел в successors(n) не может иметь большее число
• если количество узлов, достижимых из n, больше или равно |V| / 2, тогда все узлы в ancestors(n) будут иметь большее число

Как мы можем это использовать?

1. При создании графика также создайте транспонированный график. Это означает, что при сохранении ребра a-›b вы сохраняете b-›a в транспонированном графе.
2. Создайте массив, в котором хранятся узлы, которые следует игнорировать, инициализируйте его с помощью false
3. Реализуйте функцию на основе DFS, которая определяет, имеет ли данный узел количество доступных узлов >= |V| / 2 (см. ниже).
4. В этой функции игнорируйте узлы, помеченные как игнорируемые.
5. Если для узла n количество узлов меньше, чем |V| / 2, пометить все узлы в successors(n) как игнорируемые
6. В противном случае подсчитайте все узлы в ancestors(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 вы начинаете с самого большого идентификатора узла), он сокращается до 4 секунд, но это немного похоже на мошенничество ^^