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

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

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

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

Ответ 1

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

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

Следующим шагом будет свернуть каждый сильно связанный компонент в один node. Поскольку узлы внутри одного и того же компонента имеют одинаковые данные и, следовательно, в основном одинаковы, эта операция на самом деле не изменяет график. Созданный "super node" наследует все ребра, выходящие или входящие в узлы компонента из узлов вне компонента.

Поскольку мы свернули все сильно связанные компоненты, в результирующем графе не будет циклов (почему? потому что, если бы был цикл, образованный результирующими узлами, все они были бы помещены в один и тот же компонент в первую очередь). Получаемый граф теперь является Directed Acyclic Graph. Нет циклов, и простая глубина сначала проходит от всех узлов с индексом = 0 (т.е. узлами, у которых нет входящих ребер), распространение данных из каждого node на его соседние узлы (то есть его "дети" ) должно получить работа выполнена.