Направленный обход ациклического графа ... помогите?

Question

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

Вот правила:

• есть n корневых узлов (Iназовите их "источниками")
• есть n конечные узлы
• исходные узлы имеют числовое значение
• нисходящие узлы (я называю их "рабочий")узлы) предварительно выполнять различные операции над входящими значениями, такие как Add, Mult и т. д.

Как видно из приведенного ниже графика, узлы a, b и c должны бытьобрабатывается до d, e или f.

Как правильно ходить по этому дереву?

Answer 1

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

Линеаризация, насколько я помню, в основном сортируется в порядке, который соответствует инварианту, который для всех узлов (Node_X), имеющих выходную степень по отношению к любому другому заданному узлу NodeA, NodeX появляется до NodeA.

Это будет означать, что из вашего примера сначала будут обрабатываться узлы a, b и d. Узел c вторым. Узлы е и f, последние.

http://en.wikipedia.org/wiki/Topological_sorting

Answer 2

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

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