Поскольку граф циклический (то есть может содержать циклы), я бы сначала разбил его на сильно связанные компоненты. сильно связанный компонент ориентированного графа - это подграф, где каждый узел доступен из любого другого узла в том же подграфе.Это дало бы набор подграфов.Обратите внимание, что сильно связанный компонент более чем одного узла фактически является циклом.
Теперь в каждом компоненте любая информация в одном узле будет в конечном итоге попадать в каждый другой узел графа (поскольку все они достижимы).Таким образом, для каждого подграфа мы можем просто взять все данные со всех узлов в нем и сделать так, чтобы у каждого узла был одинаковый набор данных.Не нужно продолжать проходить циклы.Кроме того, в конце этого шага все узлы в одном и том же компоненте содержат абсолютно одинаковые данные.
Следующим шагом будет свертывание каждого сильно связанного компонента в один узел.Поскольку все узлы в одном и том же компоненте имеют одинаковые данные и, следовательно, в основном одинаковы, эта операция не меняет график.Вновь созданный «супер узел» унаследует все ребра, выходящие или входящие в узлы компонента, от узлов вне компонента.
Поскольку мы свернули все сильно связанные компоненты,в результирующем графе не будет циклов (почему? потому что, если бы в результирующих узлах был цикл, все они были бы помещены в один и тот же компонент в первую очередь).Результирующий граф теперь является Направленным ациклическим графом .Циклов не существует, и простой поиск глубины из всех узлов с indegree = 0 (т. Е. Узлов, у которых нет входящих ребер), распространяющих данные от каждого узла к соседним узлам (т. Е. Его «потомкам»), должен выполнить работу.