Нахождение списка общих потомков (потомков) для любых двух узлов в циклическом графе

Question

У меня есть циклический ориентированный граф, и мне было интересно, есть ли какой-нибудь алгоритм (предпочтительно оптимальный), чтобы составить список общих потомков между любыми двумя узлами? Что-то почти противоположное тому, что делает самый низкий общий предок (LCA).

Answer 1

Как предполагает user1990169, вы можете вычислить набор вершин, достижимых из каждой из начальных вершин, используя DFS, а затем вернуть пересечение.

Если вы планируете делать это многократно на одном и том же графе, то, возможно, стоит сначала вычислить и сжать сильные компоненты для супервершин, представляющих набор вершин. В качестве побочного эффекта вы можете получить топологический порядок на супервертах. Это позволяет параллельному данным алгоритму вычислять достижимость из нескольких начальных вершин одновременно. Инициализируйте все метки вершин в {}, Для каждой начальной вершины vустановите ярлык на {v}, Теперь смести все вершины w в топологическом порядке, обновление метки wвне соседей x установив его в союз xярлык и wлейбл. Используйте наборы битов для компактного, эффективного представления наборов. Недостатком является то, что мы не можем сократить, как при вычислениях с одной достижимостью.

Answer 2

Почему бы просто не поменять направление края и использовать LCA?

Answer 3

Я бы порекомендовал использовать DFS ( поиск в глубину).

For each input node
    Create a collection to store reachable nodes
    Perform a DFS to find reachable nodes
        When a node is reached
            If it's already stored stop searching that path // Prevent cycles
            Else store it and continue

Find the intersection between all collections of nodes

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

---

При реализации этого имейте в виду, что будет несколько особых случаев, которые вы можете искать для дальнейшей оптимизации поиска, таких как:

• Если у входного узла нет вершин, то нет общих узлов
• Если один входной узел (A) достигает другого входного узла (B), то A может достичь всего, что может B.
  Это означает, что алгоритм не должен быть запущен на B.
• и т.п.