Обход циклического направленного графика

Question

У меня есть циклический направленный график. Начиная с листьев, я хочу распространять данные, прикрепленные к каждому узлу ниже по течению ко всем узлам, которые доступны от этого узла. В частности, мне нужно поддерживать толкание данных вокруг любых циклов, которые достигаются, пока циклы не стабилизируются.

Я полностью уверен, что это проблема обхода на складе. Тем не менее, у меня есть достаточно трудности, пытаясь найти подходящий алгоритм --- Я думаю, что я скучаю по нескольким решающим поисковым ключевым словам.

Прежде чем я попытаюсь написать свой собственный алгоритм O (N ^ 3), может кто-нибудь указать мне на правильное решение? И что является Эта конкретная проблема называется?

Answer 1

Поскольку график циклический (т.е. может содержать циклы), сначала сначала сломал его в сильно связанные компоненты. А. Сильно связанный компонент Из направленного графика представляет собой подграф, где каждый узел достижится от каждого другого узла в том же подграфе. Это даст набор подграфов. Обратите внимание, что настоятельно подключенный компонент более одного узла эффективно является циклом.

Теперь, в каждом компонент, любая информация в одном узле в конечном итоге в конечном итоге в конечном итоге в любой другой узел графика (поскольку все они доступны). Таким образом, для каждого подграфа мы можем просто принять все данные из всех узлов в нем и сделать каждый узел иметь тот же набор данных. Нет необходимости продолжать проходить через циклы. Кроме того, в конце этого шага все узлы в одном компоненте содержит точно такие же данные.

Следующим шагом было бы разрушение каждого сильно связанного компонента в один узел. В качестве узлов в том же компонент все имеют одни и те же данные, и поэтому в основном то же самое, эта операция на самом деле не меняет график. Вновь созданный «Super Node» наследует все края, выходящие или входящие в узлы компонента от узлов за пределами компонента.

Поскольку мы рухнули все сильно связанные компоненты, в результирующем графике не будет циклов (почему? Потому что произошло цикл, образованный резульными узлами, они все были бы помещены в тот же компонент в первую очередь). Результирующий график теперь Направленный ациклический график. Отказ Нет циклов, а простая глубина, первая обход от всех узлов с Indegree = 0 (т.е. узлами, которые не имеют входящих краев), размножая данные с каждого узла к его соседним узлам (т.е. его «детям»), должны выполнить работу Отказ