Как записать DAG для прохода по ациклическому ориентированному графу, используя C#?

Question

[pavlik 322]

Как записать DAG для прохода по? ациклическому ориентированному графу , используя C#?
Я имею в виду пройти от начало до конца:

Comments

[Wataru]

В чем вопрос-то состоит? Вы не можете просто постаивть вопросительный знак после подлежащего. Переформулируйте ваш вопрос.

Что значит "оптимальный обход" для вас?

[pavlik 322]

Wataru, Спасибо, поправил. Оптимальный, ну как минимум, чтобы работал быстрее, чем просто foreach-ом по всем узлам))

[Wataru]

pavlik 322, Нет, вам надо описать, что вам нужно от обхода. Вот есть у вас граф, что вам надо с ним сделать?

Ничего быстрее foreach, если вам надо просто перебрать все вершины в графе в любом порядке нет.

[pavlik 322]

Wataru, Я говорил о том, чтобы по рёбрам пройти от начала и до конца в таком порядке

[Wataru]

pavlik 322, Давайте вот этот ваш пример разберем. У вас есть DAG, в каждой вершине которого или операция, или это лист с буквой. Так? У вас всегда в графе одна "корневая" вершина? Это запись арифметического выражения и вы хотите его посчитать, т.е. вам надо обойти все вершины в топологическом порядке снизу вверх?

[pavlik 322]

Wataru, Да!

Answer 1

[Wataru]

Раз вам надо обойти врешины в топлолгическом порядке, вам нужна топологическая сортировка. Если у вас только одна корневая вершина, то можно и проще - тут сработает любой обход: в ширину или в глубину из корневой вершины. Если корневых вершин несколько, то надо будет использовать какой-либо алгоритм топологической сортировки. Гуглите его. Есть алгоритм основанный на двух обходах в глубину, или нечто основанное на обходе в ширину.

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

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

Comments

[pavlik 322]

Вопрос как вообще обозначать графы? Я делал это через один список узлов с числовыми значениями, два для рёбер, в одном есть входные, в другом соответсвенно по индексу выходные.
Т.е.:
[4, 7, 8, 1, 0] - список узлов, первые две корневые вершины графа(ну может быть и больше или меньше), третий выход

[0, 3, 4]-рёбра(список индексов узлов). Вход
[4, 2, 3]-рёбра(список индексов узлов). Выход.
Просто по-моему оказалось, что их обозначают по другому

[Wataru]

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

[pavlik 322]

Wataru, Спасибо, только тогда хранить веса?

[Wataru]

pavlik 322, Надо в списке хранить пары {вершина, вес}. Или можно держать 2 списка, один для вершин, другой для весов.

[pavlik 322]

Wataru, И получается, что алгоритм поиска в глубину также требует, чтобы у любой связи была только одна входная связь?

[Wataru]

pavlik 322, Не понял вопроса. У связи была связь? Входная связь? В графе есть вершины и ребра. Переформулируйте ваш вопрос в этих терминах.

[pavlik 322]

Wataru, Что направленных рёбер ведущих к данному узлу не может быть больше одного

[Wataru]

pavlik 322, Для обхода в глубину и для топологической сортировки это не проблема. Раз у вас, судя по некоторым замечаниям, может быть несколько корневых вершин, то у вас будет топологическая сортировка, которая работает через обход в глубину. У вас там будут пометки вершин, в которых вы уже были, и обход не заходит в вершину второй раз.

[pavlik 322]

Wataru, Как можно пройти дальше, если не все рёбра ведущие к узлу были пройдены?

[Wataru]

pavlik 322,
Почитайте статьи про топологическую сортировку, все должно стать понятно.

Или смотрите на это с другой стороны. Функция считает значение в вершине. Если оно было уже подсчитано, то просто возвращает его. Иначе вызывается рекурсивно от всех детей, чтобы подсчитать их, применяет операцию в текущей вершине, сохраняет значение, и возвращает его.

[pavlik 322]

Wataru, И почему так важно количество корневых узлов? Разве мы не можем объединить все корневые узлы одни общим?

[Wataru]

pavlik 322, Если корневой узел один, то сразу ясно, откуда надо запускаться, и обход обойдет все вершины. Если их несколько, то нет гарантии, что один запуск обойдет все. Поэтому надо будет в цикле обходить все вершины и считать их, если они не подсчитаны.

Объединить все коренвые узлы общим можно, да.

[pavlik 322]

Wataru, Тогда почему так не делают?

[Wataru]

pavlik 322, Потому что это не проще чем просто запустить обход от всех вершин. Ведь вам все равно обычно надо все корневые вершины еще и найти в графе. Так что это такой же цикл по всем вершинам, но при этом надо граф менять и как-то помнить, что вот эта новая вершина корень - фиктивная и где-то дальше ее отдельно обрабатывать.

[pavlik 322]

Wataru, но получается время выполнения одинаковое?

[Wataru]

pavlik 322, Да, время выполнения везде линейное.