Центральный Дом Знаний - Алгоритм Тарьяна

Информационный центр "Центральный Дом Знаний"

Заказать учебную работу! Жми!



ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

      cendomzn@yandex.ru  

Наш опрос

Как Вы планируете отдохнуть летом?
Всего ответов: 903

Онлайн всего: 2
Гостей: 2
Пользователей: 0


Форма входа

Логин:
Пароль:

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

Алгоритм Тарьяна, алгоритм поиска компонент сильной связности в орграфе, работающий за линейное время.

Этот алгоритм основан на том, что:

1) Мы рассматриваем вершины в обратном топологическом порядке, поэтому, когда мы придем в конец рекурсивной функции для исходной вершины, мы не встретим ни одной вершины из той же сильной компоненты, так как все вершины, достижимые из этой, уже обработаны.

2) Обратные связи в дереве дают второй путь из одной вершины в другую и связывают сильные компоненты.

Algorithm Tarjan.gif

В основе А.Т. лежит рекурсивный поиск в глубину, в который добавлена операция проталкивания вершин в стек. Он вычисляет индекс компоненты для каждой вершины в векторе id, индексированном именами вершин, используя векторы pre и low (справа). Вектор low отслеживает вершину с наименьшим номером в прямом порядке обхода, достижимую из каждого узла через последовательность прямых связей, за которыми следует одна восходящая связь. Воспользовавшись поиском в глубину с тем, чтобы рассматривать вершины в обратном топологическом порядке, мы вычисляем для каждой вершины v максимальную точку, достижимую через обратную связь из предшественника (low[v]). Когда для вершины v выполняется pre[v]=low[v], мы выталкиваем ее из стека, а также все вершины выше ее и всем им присваиваем номер следующей компоненты.

Этот метод линеен по времени, так как в данном случае к стандартному DFS добавляется несколько операций, работающих за константу.


Лит.: Роберт Седжвик. Алгоритмы на графах = Graph algorithms — 3-е изд. — Россия, Санкт-Петербург: «ДиаСофтЮП», 2002. — С. 496. — ISBN 5-93772-054-7.

Loading

Календарь

«  Сентябрь 2019  »
ПнВтСрЧтПтСбВс
      1
2345678
9101112131415
16171819202122
23242526272829
30

Архив записей

Друзья сайта

  • Заказать курсовую работу!
  • Выполнение любых чертежей
  • Новый фриланс 24