170
правок
Изменения
Нет описания правки
|id=topsort_def
|definition=
'''Топологическая сортировка''' (англ. ''topological sort'') [[Ориентированный граф|ориентированного]] [[Основные определения теории графов|ациклического графа]] <tex>G = (V, E)</tex> представляет собой упорядочение упорядочивание [[Основные определения теории графов|вершин]] таким образом, что для любого ребра <tex>(u, v) \in E(G)</tex> номер вершины <tex>u</tex> меньше номера вершины <tex>v\ </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>
Время работы этого алгоритма соответствует времени работы алгоритма поиска в глубину, то есть равно <tex>O(|V| +|E|)</tex>.
==Пример==
* [[Использование обхода в глубину для поиска мостов]]
== Источники информации ==
*Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — с.653 — 656.— ISBN 978-5-8459-0857-5 (рус.)
* [http://habrahabr.ru/blogs/algorithm/100953/#habracut Топологическая сортировка на habrahabr]
