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

Question

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

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

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

Answer 1

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

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

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

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