Добрый день! Давно не имел дело с графами, а возникла следующая задача.

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

Пример: 

1 - 2
1 - 3
2 - 3

Ответ: 3, 2, 1 (вершина 1 зависит от 2 и 3, вторая только от 3, 3 ни от кого).

Заранее спасибо!

Это сообщение отредактировал(а) Tketano - 20.12.2011, 10:52

Это называется топологическая сортировка. Гуглите, в сети есть миллион описаний и исходников.

Берете независимую вершину, выводите, потом выводите вершины непосредственно зависимые от нее и т.д. Типичный пример рекурсии ИМХО.

Но нужно будет задать дополнительное условия.

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

Во вторых. В примере вершина 1 зависит от не тольо от 3, но и от 2. Судя по примеру, это означает что она должна идти после 2, зависящей только от 3. Но вариантов таких путей в графе может быть очень много. Поэтому надо задать условие установки приоритета - по самому короткому пути (не Ваш случай), по самому длинному пути, по-еще-какму-то-критерию-выводимому-из-наличествующих-путей.

И еще, я с графами тоже годы уже не работал. Разве бывает однонаправленный граф с циклами?

_Y_, все бы хорошо, но даже в данном примере видно что такой способ не работает.

Пример:

1 - 2
2 - 3
3 - 4
4 - 5
1 - 5

Во Вашему алгоритму получается, что выводим (в обратном порядке): 4, 3, 5, 2, 1 (как бы в ширь идет, я вас правильно понял?). Хотя, изначально, все завязано на вершине 5. Поэтому не получается)

maxdiver, спасибо! Сейчас посмотрю

maxdiver, все правильно! один из методов решения - обход в глубину с обратным выводом вершин.

Кому интересно - вот пример

Tketano, не совсем так. Я предлагал начинать от независимой вершины, т.е. в Вашем примере от 5. Видимо недостаточно понятно написал. Извиняюсь.

Но, по любому, решена проблема - и прекрассно