170
правок
Изменения
м
When you walk through a storm{{Определение|id=topsort_def|definition='''Топологическая сортировка''' (англ. ''topological sort'') [[Ориентированный граф|ориентированного]] [[Основные определения теории графов|ациклического графа]] <tex>G = (V, E)</tex> представляет собой упорядочивание [[Основные определения теории графов|вершин]] таким образом, что для любого ребра <tex>(u,v) \in E(G)</tex> номер вершины <tex>u</tex> меньше номера вершины <tex>v\ </tex>. hold your head up high}} == Применение ==Топологическая сортировка применяется в самых разных ситуациях, например при создании параллельных алгоритмов, когда по некоторому описанию алгоритма нужно составить граф зависимостей его операций и, отсортировав его топологически,определить, какие из операций являются независимыми и могут выполняться параллельно (одновременно). Примером использования топологической сортировки может служить создание карты сайта, где имеет место древовидная система разделов. Также топологическая сортировка применяется при обработке исходного кода программы в некоторых компиляторах и IDE, где строится граф зависимостей между сущностями, после чего они инициализируются в нужном порядке, либо выдается ошибка о циклической зависимости.and don't be afraid of the darkТакже с помощью топологической сортировки можно найти [[Гамильтоновы графы|гамильтонов путь]] в ациклическом графе.At the end of the storm== Постановка задачи =={{Теорема|statement=<tex>G</tex> — ациклический ориентированный граф,тогда <tex>\exists \ \varphi : V \to \{ 1..n \} , uv \in E \Rightarrow \varphi (u) < \varphi (v) </tex> |proof=is the golden skyОпределим <tex>leave[u]</tex> как порядковый номер окраски вершины <tex>u</tex> в черный цвет в результате работы [[Обход в глубину, цвета вершин|алгоритма dfs]]. Рассмотрим функцию <tex>\varphi = n + 1 - leave[u] </tex>. Очевидно,что такая функция подходит под критерий функции <tex>\varphi</tex> из условия теоремы, если выполняется следующее утверждение:and the sweet silver song of the lark.{{ЛеммаWalk on through the wind|statement=<tex>G</tex> — ациклический ориентированный граф,тогда <tex>uv \in E \Rightarrow leave[u] > leave[v]</tex>walk on through the rain|proof=Рассмотрим произвольное [[Основные определения теории графов|ребро]] <tex>(u, v)</tex>, исследуемое процедурой <tex>dfs</tex>. При исследовании вершина <tex>v</tex> не может быть серой, так как серые вершины в процессе работы <tex>dfs</tex> всегда образуют простой путь в графе, и факт попадания в серую вершину <tex>v</tex> означает, что в графе есть цикл из серых вершин, что противоречит условию утверждения. Следовательно, вершина <tex>v</tex> должна быть белой либо черной. Если вершина <tex>v</tex> — белая, то она становится потомком <tex>u</tex>, так что <tex>leave[u] > leave[v]</tex>. Если <tex>v</tex> — черная, значит, работа с ней уже завершена и значение <tex>leave[v]</tex> уже установлено. Поскольку мы все еще работаем с вершиной <tex>u</tex>, значение <tex>leave[u]</tex> еще не определено,так что, когда это будет сделано, будет выполняться неравенство <tex>leave[u] > leave[v]</tex>. Следовательно, для любого ребра <tex>(u, v)</tex> ориентированного ациклического графа выполняется условие <tex>leave[u] > leave[v]</tex>.}}Though your dreams be tossed and blownТаким образом,теорема доказана.Walk on}} == Алгоритм ==Из определения функции <tex>\varphi</tex> мгновенно следует алгоритм топологической сортировки: <font color=green>// <tex>G</tex> {{---}} исходный граф</font> '''function''' <tex>\mathtt{topologicalSort}():</tex> [[Использование обхода в глубину для поиска цикла|проверить граф <tex>G</tex> на ацикличность]] <tex>fill(\mathtt{visited}, walk on with hope false)</tex> '''for''' <tex>v \in V(G)</tex> '''if''' '''not''' <tex>\mathtt{visited}[v] </tex> <tex>\mathtt{dfs}(v) </tex> <tex>\mathtt{ans}.\mathtt{reverse}() </tex> '''function''' <tex>\mathtt{dfs}(u):</tex> <tex>\mathtt{visited}[u] = true </tex> '''for''' <tex>uv \in your heartE(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>. ==Пример==And you'll never walk aloneРаспространённая задача на топологическую сортировку {{---}} следующая. Есть <tex>n</tex> переменных, значения которых нам неизвестны. Известно лишь про некоторые пары переменных, что одна переменная меньше другой. Требуется проверить, не противоречивы ли эти неравенства, и если нет, выдать переменные в порядке их возрастания (если решений несколько — выдать любое). Легко заметить,что это в точности и есть задача о поиске топологической сортировки в графе из <tex>n</tex> вершин. you'll never walk alone==См.также==* [[Использование обхода в глубину для поиска цикла]]* [[Использование обхода в глубину для проверки связности]]* [[Использование обхода в глубину для поиска компонент сильной связности]]* [[Использование обхода в глубину для поиска точек сочленения]]* [[Использование обхода в глубину для поиска мостов]] == Источники информации ==*Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — с.653 — 656.— 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# Пример задачи на топологическую сортировку] [[Категория: Алгоритмы и структуры данных]][[Категория: Обход в глубину]]
Нет описания правки
