Использование обхода в глубину для топологической сортировки — различия между версиями
Glukos (обсуждение | вклад) (→Алгоритм) |
Glukos (обсуждение | вклад) (→Алгоритм) |
||
Строка 37: | Строка 37: | ||
} | } | ||
− | Время работы этого алгоритма соответствует времени работы алгоритма поиска в глубину, то есть равно <tex>O(V+E)</tex> | + | Время работы этого алгоритма соответствует времени работы алгоритма поиска в глубину, то есть равно <tex>O(V+E)</tex>. |
Версия 05:16, 25 октября 2011
Топологическая сортировка ориентированного ациклического графа
представляет собой такое линейное упорядочение всех его вершин, что если , то при таком упорядочении располагается до (если граф не является ациклическим, такая сортировка невозможна).Постановка задачи
Теорема: | |||||
— ациклический ориентированный граф, тогда | |||||
Доказательство: | |||||
Определим Обход в глубину, цвета вершин. Рассмотрим функцию . Очевидно, что такая функция подходит под критерий функции из условия теоремы, если выполняется следующее утверждение: как порядковый номер окраски вершины в черный цвет в результате работы алгоритма , см.
| |||||
Алгоритм
Из определения функции
мгновенно следует алгоритм топологической сортировки:doTopSort(graph G) { fill(visited, false); time = 0; for (Vertex v : v in graph G) { if (!visited[v]) { dfs(v); } } }
dfs(u) { visited[u] = true; for (Vertex v : exists edge uv) { if (!visited[v]) { dfs(v); } } topSortAnswer[u] = n - time++; }
Время работы этого алгоритма соответствует времени работы алгоритма поиска в глубину, то есть равно
.