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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (Алгоритм)
Строка 20: Строка 20:
 
Из определения функции <tex>\varphi</tex> мгновенно следует алгоритм топологической сортировки:
 
Из определения функции <tex>\varphi</tex> мгновенно следует алгоритм топологической сортировки:
  
  doTopSort(graph G) {
+
  <font color=green>// <tex>G</tex> {{---}} исходный граф</font>
    fill(visited, false);
+
'''function''' <tex>\mathtt{topologicalSort}():</tex>
    time = 0;
+
    <tex>fill(\mathtt{visited}, false)</tex>
    for (vertex v : v in graph G) {
+
    '''for''' <tex>v \in V(G)</tex>
      if (!visited[v]) {
+
        '''if''' '''not''' <tex>\mathtt{visited}[v] </tex>
          dfs(v);
+
              <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>
  
dfs(vertex u) {
 
    visited[u] = true;
 
    for (vertex v : exists edge uv) {
 
      if (!visited[v]) {
 
          dfs(v);
 
      }
 
    }
 
    topSortAnswer[u] = n - time++;
 
}
 
  
 
Время работы этого алгоритма соответствует времени работы алгоритма поиска в глубину, то есть равно <tex>O(V+E)</tex>.
 
Время работы этого алгоритма соответствует времени работы алгоритма поиска в глубину, то есть равно <tex>O(V+E)</tex>.

Версия 20:04, 11 января 2015

Топологическая сортировка ориентированного ациклического графа [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]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].

Источники

  • Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ, второе издание. Пер. с англ. — Издательский дом "Вильямс", 2007. — 1296 с. — Глава 22. Элементарные алгоритмы для работы с графами.
  • Топологическая сортировка на habrahabr