Топологическая сортировка

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

Пусть есть набор действий {A, B, C, D, E, F}, которые нужно выполнить. Причем A можно выполнить только после F, B – после С и A, С – после E, а D – после B.

В каком порядке нужно выполнять действия?

Нарисуем граф из действий: ребро идет из A в B, если B нужно делать после A.

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

Итак, результат сортировки приведенного графа таков:

Это не единственная возможная сортировка: например, вершину E можно перенести прямо перед C и т.д.

Как получить решение в общем случае?

Возьмем произвольную вершину, например, C. Обойдем в глубину все вершины, достижимые из нее: получим следующий результат: С встретилась первой, B – второй, D – третьей. Пройден еще не весь граф. Возьмем еще одну вершину (из не пройденных). Эта вершина недостижима из C – иначе она была бы пройдена – значит, ее (и все вершины, достижимые из нее) можно поставить раньше, чем C – нет необходимости ставить позже.

Пусть мы взяли вершину F: вершины F и A встанут перед C именно в названном порядке, потому что A встретилась позже, чем F.

Снова возьмем произвольную не пройденную вершину: осталась только E. Ее можно поставить перед F и перед C, то есть на первое место.

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

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

Заведем список, в который будем добавлять вершины. Мы каждый раз ставим вершину раньше всех пройденных, поэтому будем добавлять в начало списка: прошли все вершины, стоящие после данной – теперь можно добавить ее.

Итак, имея рекурсивную реализацию обхода в глубину, мы можем построить топологическую сортировку графа следующим образом:

1. Если вершина i пройдена, выйти

2. Отметить вершину i как пройденную

3. Вызвать процедуру обхода от всех вершин, смежных с i

Этот вызов добавит в список все вершины, стоящие после текущей.

4. Добавить текущую вершину в начало списка.

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

«Наивный» алгоритм нумерации вершин:

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

«Эффективный» алгоритм нумерации вершин:

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

+індивідуалка № варіанту то є № області в Україні

[21:39:18] Pavlo Denysyuk: з обл.центру прокладайте дорогу

[21:39:51] Pavlo Denysyuk: вершини гарафа обл.центр та районний центр

[21:40:03] Pavlo Denysyuk: вага ребра, відстань в км

Дата добавления: 2015-10-13