Автономный алгоритм наименьших общих предков Tarjans - Tarjans off-line lowest common ancestors algorithm - Wikipedia

Не путать с Алгоритм сильносвязных компонентов Тарьяна.

В Информатика, Автономный алгоритм наименьших общих предков Тарьяна является алгоритм для вычислений самые низкие общие предки для пар узлов в дереве на основе союз-находка структура данных. Самый низкий общий предок двух узлов d и е в укоренившееся дерево Т это узел грамм это предок обоих d и е и это имеет наибольшую глубину в Т. Он назван в честь Роберт Тарджан, открывший эту технику в 1979 году. Алгоритм Тарьяна - автономный алгоритм; то есть, в отличие от других алгоритмов с наименьшим общим предком, он требует, чтобы все пары узлов, для которых требуется наименьший общий предок, были указаны заранее. В простейшей версии алгоритма используется структура данных объединение-поиск, которая, в отличие от других структур данных с наименьшими общими предками, может занимать больше, чем постоянное время на операцию, когда количество пар узлов аналогично количеству узлов. Позднее уточнение Габоу и Тарджан (1983) ускоряет алгоритм до линейное время.

Псевдокод

Псевдокод ниже определяет наименьшего общего предка каждой пары в п, учитывая корень р дерева, в котором дочерние элементы узла п находятся в наборе n. дети. Для этого автономного алгоритма набор п необходимо уточнять заранее. Он использует MakeSet, Находить, и Союз функции непересекающийся лес. MakeSet (u) удаляет ты в одноэлементный набор, Найдите (u) возвращает стандартный представитель множества, содержащего ты, и Союз (u, v) объединяет набор, содержащий ты с набором, содержащим v.TarjanOLCA (р) сначала вызывается в корне р.

функция TarjanOLCA (u) является    MakeSet (u) u.ancestor: = u для каждого v в u. дети делать        TarjanOLCA (v) Союз (u, v) Найдите (u) .ancestor: = u u.color: = черный для каждого v такой, что {u, v} в п делать        если v.color == черный тогда            print «Самый низкий общий предок Тарьяна для« + u + »и« + v + »равен« + Find (v) .ancestor + ».»

Каждый узел изначально белый, а после посещения его и всех его дочерних узлов он окрашивается в черный цвет.

Для каждой пары узлов {u, v} подлежат исследованию:

  • Когда v уже черный (а именно, когда v приходит раньше ты в обходе дерева после заказа): После ты окрашен в черный цвет, самый низкий общий предок этой пары доступен как Найдите (v) .ancestor, но только пока LCA ты и v не окрашен в черный цвет.
  • Иначе: Один раз v окрашен в черный цвет, LCA будет доступен как Найдите (u) .ancestor, в то время как LCA не окрашена в черный цвет.

Для справки, вот оптимизированные версии MakeSet, Находить, и Союз для непересекающийся лес:

функция MakeSet (x) является    x.parent: = x x.rank: = 1 функция Союз (x, y) является    xRoot: = Найти (x) yRoot: = Найти (y) если xRoot.rank> yRoot.rank тогда        yRoot.parent: = xRoot иначе если xRoot.rank тогда        xRoot.parent: = yRoot иначе если xRoot.rank == yRoot.rank тогда        yRoot.parent: = xRoot xRoot.rank: = xRoot.rank + 1 функция Найти (x) является    если x.parent! = x тогда       x.parent: = Найти (x.parent) возвращаться x.parent

Рекомендации

  • Gabow, H.N .; Тарьян, Р.Э. (1983), "Алгоритм линейного времени для частного случая несвязного объединения множеств", Материалы 15-го симпозиума ACM по теории вычислений (STOC), стр. 246–251, Дои:10.1145/800061.808753.