Алгоритм Тарьяна: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Jumpow (обсуждение | вклад) Нет описания правки |
РоманСузи (обсуждение | вклад) дополнение иллюстрации, викификация |
||
Строка 1:
[[Файл:Tarjan's Algorithm Animation.gif||thumb|Анимация алгоритма Тарьяна]]
'''Алгоритм Тарьяна''' — алгоритм поиска [[Компонента сильной связности в орграфе|компонент сильной связности]] в [[орграф]]е, работающий за линейное время.
Этот алгоритм основан на том, что:
Строка 14 ⟶ 16 :
== Время работы ==
Алгоритм имеет временну́ю сложность <math>\mathrm{O}(|V|+|E|)</math>, где <math>|E|</math> — количество рёбер, а <math>|V|</math> — вершин графа{{sfn|Джереми Сик и др.|2006}}.
== См. также ==▼
[[Алгоритм нахождения компонент сильной связанности]] — аналогичный алгоритм, использующий поиск в глубину.▼
▲== См. также ==
▲[[Алгоритм нахождения компонент сильной связанности]]
== Примечания ==
Строка 49 ⟶ 51 :
|isbn = 5-93772-054-7
}}
* {{книга|автор=Джереми Сик, Лай-Кван Ли, Эндрю Ламсдэйн.|заглавие=C++ Boost Graph Library|издательство=Питер|год=2006|isbn=5-469-00352-3|страницы=
__NOTOC__
| |||