Русскоязычное программирование

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.



Алгоритм Тарьяна

Сообщений 1 страница 2 из 2

1

1972, Tarjan, R. E., "Depth-first search and linear graph algorithms", SIAM Journal on Computing, 1 (2): 146–160

ищет компоненты связности направленного графа за линейное (от суммы количества рёбер и вершин) время.

[html]
<a href="https://ru.wikipedia.org/wiki/Алгоритм_Тарьяна">Wikipedia (ru)</a>
<br />
<a href="https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm">Wikipedia (en)</a>
[/html]

Отредактировано Лис (2017-11-06 07:47:54)

0

2

Оказывается ещё есть "алгоритм Хопкрофта-Тарьяна", позволяет проверить граф на планарнсть за линейное время.

0