ПО, ЭВМ и АСУ из Таможенного Союза

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

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

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

Страница: 1

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

1

  • Автор: ВежливыйЛис
  • Администратор
  • Зарегистрирован: 2017-03-25
  • Приглашений: 0
  • Сообщений: 1103
  • Уважение: [+2/-1]
  • Позитив: [+4/-1]
  • Провел на форуме:
    7 дней 7 часов
  • Последний визит:
    2024-02-01 16:07:42

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

  • Автор: ВежливыйЛис
  • Администратор
  • Зарегистрирован: 2017-03-25
  • Приглашений: 0
  • Сообщений: 1103
  • Уважение: [+2/-1]
  • Позитив: [+4/-1]
  • Провел на форуме:
    7 дней 7 часов
  • Последний визит:
    2024-02-01 16:07:42

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

0

Страница: 1