170
правок
Изменения
м
'''function''' <tex>\mathtt{dfs}(u):</tex>
Нет описания правки
{{Определение|id=topsort_def|definition='''Топологическая сортировка''' (англ. ''topological sort'') [[Ориентированный граф|ориентированного]] [[Основные определения теории графов|ациклического графа]] <tex>G = (V, E)</tex> представляет собой упорядочение упорядочивание [[Основные определения теории графов|вершин]] таким образом, что для любого ребра <tex>(u, v) \in E(G)</tex> номер вершины <tex>u</tex> меньше номера вершины <tex>v\ </tex>. }}
== Применение ==
Топологическая сортировка применяется в самых разных ситуациях, например при создании параллельных алгоритмов, когда по некоторому описанию алгоритма нужно составить граф зависимостей его операций и, отсортировав его топологически, определить, какие из операций являются независимыми и могут выполняться параллельно (одновременно). Примером использования топологической сортировки может служить создание карты сайта, где имеет место древовидная система разделов. Также топологическая сортировка применяется при обработке исходного кода программы в некоторых компиляторах и IDE, где строится граф зависимостей между сущностями, после чего они инициализируются в нужном порядке, либо выдается ошибка о циклической зависимости.
Также с помощью топологической сортировки можно найти [[Гамильтоновы графы|гамильтонов путь]] в ациклическом графе.
== Постановка задачи ==
<font color=green>// <tex>G</tex> {{---}} исходный граф</font>
'''function''' <tex>\mathtt{topologicalSort}():</tex>
[[Использование обхода в глубину для поиска цикла|проверить граф <tex>G</tex> на ацикличность]]
<tex>fill(\mathtt{visited}, false)</tex>
'''for''' <tex>v \in V(G)</tex>
<tex>\mathtt{dfs}(v) </tex>
<tex>\mathtt{ans}.\mathtt{reverse}() </tex>
<tex>\mathtt{visited}[u] = true </tex>
'''for''' <tex>uv \in E(G)</tex>
Время работы этого алгоритма соответствует времени работы алгоритма поиска в глубину, то есть равно <tex>O(|V| +|E|)</tex>. ==Пример==Распространённая задача на топологическую сортировку {{---}} следующая. Есть <tex>n</tex> переменных, значения которых нам неизвестны. Известно лишь про некоторые пары переменных, что одна переменная меньше другой. Требуется проверить, не противоречивы ли эти неравенства, и если нет, выдать переменные в порядке их возрастания (если решений несколько — выдать любое). Легко заметить, что это в точности и есть задача о поиске топологической сортировки в графе из <tex>n</tex> вершин. ==См. также==* [[Использование обхода в глубину для поиска цикла]]* [[Использование обхода в глубину для проверки связности]]* [[Использование обхода в глубину для поиска компонент сильной связности]]* [[Использование обхода в глубину для поиска точек сочленения]]* [[Использование обхода в глубину для поиска мостов]]
== Источники информации ==* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. — Алгоритмы: построение и анализ, второе 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 20072010. — 1296 с. 653 — Глава 22656. Элементарные алгоритмы для работы с графами— ISBN 978-5-8459-0857-5 (рус.)
* [http://habrahabr.ru/blogs/algorithm/100953/#habracut Топологическая сортировка на habrahabr]
* [http://e-maxx.ru/algo/finding_cycle MAXimal :: algo :: Топологическая сортировка]
* [http://informatics.mccme.ru/mod/statements/view3.php?id=256&chapterid=166# Пример задачи на топологическую сортировку]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]
