Использование обхода в глубину для топологической сортировки — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 30 промежуточных версий 7 участников)
Строка 1: Строка 1:
'''Топологическая сортировка''' ориентированного ациклического графа <tex>G = (V, E)</tex> представляет собой такое линейное упорядочение всех его вершин, что если <tex>(u, v) \in E(G)</tex>, то <tex>u</tex> при таком упорядочении располагается до <tex>v\ </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, где строится граф зависимостей между сущностями, после чего они инициализируются в нужном порядке, либо выдается ошибка о циклической зависимости.
 +
 
 +
Также с помощью топологической сортировки можно найти [[Гамильтоновы графы|гамильтонов путь]] в ациклическом графе.
  
 
== Постановка задачи ==
 
== Постановка задачи ==
Строка 5: Строка 14:
 
|statement=<tex>G</tex> — ациклический ориентированный граф, тогда <tex>\exists \ \varphi : V \to \{ 1..n \} , uv \in E \Rightarrow \varphi (u) < \varphi (v) </tex>  
 
|statement=<tex>G</tex> — ациклический ориентированный граф, тогда <tex>\exists \ \varphi : V \to \{ 1..n \} , uv \in E \Rightarrow \varphi (u) < \varphi (v) </tex>  
 
|proof=
 
|proof=
Определим <tex>leave[u]</tex> как порядковый номер окраски вершины <tex>u</tex> в черный цвет в результате работы алгоритма <tex>dfs</tex>, см. [[Обход в глубину, цвета вершин]]. Рассмотрим функцию <tex>\varphi = n + 1 - leave[u] </tex>. Очевидно, что такая функция подходит под критерий функции <tex>\varphi</tex> из условия теоремы, если выполняется следующее утверждение:
+
Определим <tex>leave[u]</tex> как порядковый номер окраски вершины <tex>u</tex> в черный цвет в результате работы [[Обход в глубину, цвета вершин|алгоритма dfs]]. Рассмотрим функцию <tex>\varphi = n + 1 - leave[u] </tex>. Очевидно, что такая функция подходит под критерий функции <tex>\varphi</tex> из условия теоремы, если выполняется следующее утверждение:
{{Утверждение
+
{{Лемма
 
|statement=<tex>G</tex> — ациклический ориентированный граф, тогда <tex>uv \in E \Rightarrow leave[u] > leave[v]</tex>
 
|statement=<tex>G</tex> — ациклический ориентированный граф, тогда <tex>uv \in E \Rightarrow leave[u] > leave[v]</tex>
 
|proof=
 
|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>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>.
 
}}
 
}}
 +
Таким образом, теорема доказана.
 
}}
 
}}
 +
 +
== Алгоритм ==
 +
Из определения функции <tex>\varphi</tex> мгновенно следует алгоритм топологической сортировки:
 +
 +
<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>
 +
        '''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 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> вершин.
 +
 +
==См. также==
 +
* [[Использование обхода в глубину для поиска цикла]]
 +
* [[Использование обхода в глубину для проверки связности]]
 +
* [[Использование обхода в глубину для поиска компонент сильной связности]]
 +
* [[Использование обхода в глубину для поиска точек сочленения]]
 +
* [[Использование обхода в глубину для поиска мостов]]
 +
 +
== Источники информации ==
 +
*Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ, 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# Пример задачи на топологическую сортировку]
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Обход в глубину]]

Текущая версия на 19:43, 4 сентября 2022

Определение:
Топологическая сортировка (англ. topological sort) ориентированного ациклического графа [math]G = (V, E)[/math] представляет собой упорядочивание вершин таким образом, что для любого ребра [math](u, v) \in E(G)[/math] номер вершины [math]u[/math] меньше номера вершины [math]v\ [/math].


Применение

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

Также с помощью топологической сортировки можно найти гамильтонов путь в ациклическом графе.

Постановка задачи

Теорема:
[math]G[/math] — ациклический ориентированный граф, тогда [math]\exists \ \varphi : V \to \{ 1..n \} , uv \in E \Rightarrow \varphi (u) \lt \varphi (v) [/math]
Доказательство:
[math]\triangleright[/math]

Определим [math]leave[u][/math] как порядковый номер окраски вершины [math]u[/math] в черный цвет в результате работы алгоритма dfs. Рассмотрим функцию [math]\varphi = n + 1 - leave[u] [/math]. Очевидно, что такая функция подходит под критерий функции [math]\varphi[/math] из условия теоремы, если выполняется следующее утверждение:

Лемма:
[math]G[/math] — ациклический ориентированный граф, тогда [math]uv \in E \Rightarrow leave[u] \gt leave[v][/math]
Доказательство:
[math]\triangleright[/math]
Рассмотрим произвольное ребро [math](u, v)[/math], исследуемое процедурой [math]dfs[/math]. При исследовании вершина [math]v[/math] не может быть серой, так как серые вершины в процессе работы [math]dfs[/math] всегда образуют простой путь в графе, и факт попадания в серую вершину [math]v[/math] означает, что в графе есть цикл из серых вершин, что противоречит условию утверждения. Следовательно, вершина [math]v[/math] должна быть белой либо черной. Если вершина [math]v[/math] — белая, то она становится потомком [math]u[/math], так что [math]leave[u] \gt leave[v][/math]. Если [math]v[/math] — черная, значит, работа с ней уже завершена и значение [math]leave[v][/math] уже установлено. Поскольку мы все еще работаем с вершиной [math]u[/math], значение [math]leave[u][/math] еще не определено, так что, когда это будет сделано, будет выполняться неравенство [math]leave[u] \gt leave[v][/math]. Следовательно, для любого ребра [math](u, v)[/math] ориентированного ациклического графа выполняется условие [math]leave[u] \gt leave[v][/math].
[math]\triangleleft[/math]
Таким образом, теорема доказана.
[math]\triangleleft[/math]

Алгоритм

Из определения функции [math]\varphi[/math] мгновенно следует алгоритм топологической сортировки:

// [math]G[/math] — исходный граф
function [math]\mathtt{topologicalSort}():[/math]
    проверить граф [math]G[/math] на ацикличность
    [math]fill(\mathtt{visited}, false)[/math]
    for [math]v \in V(G)[/math]
        if not [math]\mathtt{visited}[v] [/math]
             [math]\mathtt{dfs}(v) [/math]
    [math]\mathtt{ans}.\mathtt{reverse}() [/math]

function [math]\mathtt{dfs}(u):[/math]
    [math]\mathtt{visited}[u] = true [/math]
    for [math]uv \in E(G)[/math]
        if not [math]\mathtt{visited}[v] [/math]
            [math]\mathtt{dfs}(v) [/math]
    [math]\mathtt{ans}.\mathtt{pushBack}(u) [/math]


Время работы этого алгоритма соответствует времени работы алгоритма поиска в глубину, то есть равно [math]O(|V| + |E|)[/math].

Пример

Распространённая задача на топологическую сортировку — следующая. Есть [math]n[/math] переменных, значения которых нам неизвестны. Известно лишь про некоторые пары переменных, что одна переменная меньше другой. Требуется проверить, не противоречивы ли эти неравенства, и если нет, выдать переменные в порядке их возрастания (если решений несколько — выдать любое). Легко заметить, что это в точности и есть задача о поиске топологической сортировки в графе из [math]n[/math] вершин.

См. также

Источники информации