Изменения

{{Определение|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, а именно где строится граф зависимостей между сущностями, после чего они инициализируются в нужном порядке, либо выдается ошибка о циклической зависимости. Также с помощью топологической сортировки можно найти [[Гамильтоновы графы|гамильтонов путь]] в ациклическом графе.

{{УтверждениеЛемма

doTopSort<font color=green>// <tex>G</tex> {{---}} исходный граф</font> '''function''' <tex>\mathtt{topologicalSort}(graph ):</tex> [[Использование обхода в глубину для поиска цикла|проверить граф <tex>G) {</tex> на ацикличность]] <tex>fill(\mathtt{visited}, false);</tex> time = 0; '''for''' <tex>v \in V(G)</tex> '''if''' '''not''' <tex>\mathtt{visited}[v] </tex> for <tex>\mathtt{dfs}(vertex v ) </tex> <tex>\mathtt{ans}.\mathtt{reverse}() </tex> '''function''' <tex>\mathtt{dfs}(u): v </tex> <tex>\mathtt{visited}[u] = true </tex> '''for''' <tex>uv \in graph E(G) {</tex> '''if (!''' '''not''' <tex>\mathtt{visited}[v]) </tex> <tex>\mathtt{ dfs}(v);</tex> <tex>\mathtt{ans}.\mathtt{pushBack}(u) </tex>  Время работы этого алгоритма соответствует времени работы алгоритма поиска в глубину, то есть равно <tex>O(|V| + |E|)</tex>. ==Пример== Распространённая задача на топологическую сортировку {{---} }следующая. Есть <tex>n</tex> переменных, значения которых нам неизвестны. Известно лишь про некоторые пары переменных, что одна переменная меньше другой. Требуется проверить, не противоречивы ли эти неравенства, и если нет, выдать переменные в порядке их возрастания (если решений несколько — выдать любое). Легко заметить, что это в точности и есть задача о поиске топологической сортировки в графе из <tex>n</tex> вершин.

dfs(vertex u) {==См. также== visited* [u[Использование обхода в глубину для поиска цикла]] = true; for (vertex v : exists edge uv) {* [[Использование обхода в глубину для проверки связности]] if (!visited* [v[Использование обхода в глубину для поиска компонент сильной связности]]) { dfs(v);* [[Использование обхода в глубину для поиска точек сочленения]] } } topSortAnswer* [[uИспользование обхода в глубину для поиска мостов]] = n - time++; }

Время работы этого алгоритма соответствует времени работы алгоритма поиска в глубину== Источники информации ==*Томас Х. Кормен, то есть равно <tex>OЧарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — с.653 — 656.— ISBN 978-5-8459-0857-5 (V+Eрус.)<* [http://habrahabr.ru/blogs/algorithm/100953/#habracut Топологическая сортировка на habrahabr]* [http://e-maxx.ru/algo/finding_cycle MAXimal :: algo :: Топологическая сортировка]* [http://informatics.mccme.ru/mod/statements/tex>view3.php?id=256&chapterid=166# Пример задачи на топологическую сортировку]

== Источники ==* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. [[Категория: Алгоритмы: построение и анализ, второе издание. Пер. с англ. — Издательский дом "Вильямс", 2007. — 1296 с. — Глава 22. Элементарные алгоритмы для работы с графами.структуры данных]]* [http[Категория://habrahabr.ru/blogs/algorithm/100953/#habracut Топологическая сортировка на habrbabrОбход в глубину]]