Тарџанов алгоритам за налажење јако повезаних компоненти

Тарџанов алгоритам за налажење јако повезаних компоненти
	Анимација Тарџановог алгоритма
Структура података	Граф
Најгора перформанца

Тарџанов алгоритам (назван по свом проналазачу, Роберту Тарџану^[1]) је алгоритам теорије графова, за налажење јако повезаних компоненти у графу. Иако претходи хронолошки, може се сматрати побољшаном верзијом Косарајуовог алгоритма, и може се поредити по ефикасности са алгоритмом за налажење јаких компоненти, заснованим на путу.

Преглед

Алгоритам на улазу добија усмерен граф, а на излазу даје партицију чворова графа у јаким компонентама графа. Сваки чвор графа се појављује у једној јако повезаној компоненти, чак и ако то значи да се чвор појављује у јако повезаној компоненти сам (као што је случај са дрволиким деловима графа, или кад чвор нема ни претходника ни следбеника).

Основна идеја алгоритма је следећа: обилазак у дубину почиње од произвољног чвора (и следеће претраге у дубину су спроведене на сваком чвору који није још увек пронађен). Претрага не испитује чворове који су вец испитани. Јако повезане компоненте формирају подстабла стабла претраге, коренове од којих су коренови јако повезане компоненте.

Чворови се стављају на стек, по редоследу у ком су посећени. Кад се претрага врати из подстабла, чворови се скидају са стека и одређено је да ли је сваки чвор корен јако повезане компоненте. Ако је чвор корен јако повезане компоненте, тада и сви чворови који су скинути пре њега формирају ту јако повезану компоненту.

Својства корена

Срж алгоритма је у одређивању да ли је чвор корен јако повезане компоненте. Концепт "корена" примењује се само на овај алгоритам (ван овог алгоритма, ниједна јако повезана компонента нема "корени" чвор). Корени чвор је једноставно први чвор јако повезане компоненте који је посећен током претраге у дубину. Када је чвор идентификован као корени чвор, једном када се рекурзија над његовим следбеником заврши, сви чворови на стеку изнад корена формирају комплетну јако повезану компоненту.

Да би се пронашао корен, сваком чвору придружен је индекс претраге у дубину, в.индеx, који нумерише чворове узастопно у редоследу у којем су посећени. Поред тога, сваком је додељена вредност в.лоwлинк која је једнака најмањем индексу чвора који је достижан из в, и увек је мања или једнака в.индеx, ако ниједан други чвор није достижан из в. Стога је в корен јако повезане компоненте ако и само ако је в.лоwлинк == в.индеx. Вредност в.лоwлинк је израчуната током претраге у дубину, тако да је увек познат кад је потребан.

Алгоритам у псеудокоду

 ulaz: graf G = (V, E)
 izlaz: skup jako povezanih komponenti (skupovi čvorova)
  index := 0
 S := empty
 for each v in V do
   if (v.index je nedefinisan) then
     strongconnect(v)
   end if
 repeat
 function strongconnect(v)
   // Postavlja index za v na najmanji neiskorisćeni index
   v.index := index
   v.lowlink := index
   index := index + 1
   S.push(v)
  // Razmatranje sledbenika čvora v
   for each (v, w) in E do
     if (w.index is undefined) then
       // Sledbenik w nije posećen, rekurzija kreće iz njega
       strongconnect(w)
       v.lowlink := min(v.lowlink, w.lowlink)
     else if(w is in S) then
       // Sledbenik w je u steku S i stoga je u trenutnoj JPK
       v.lowlink := min(v.lowlink, w.index)
     end if
   repeat
  // Ako je v koreni čvor, skini sa steka i generiši JPK
   if (v.lowlink = v.index) then
     započni novu povezanu komponentu
     repeat
       w := S.pop()
       dodaj w trenutnoj jako povezanoj komponenti
     until (w = v)
     stavi na izlaz jako povezanu komponentu
   end if
 end function

Променљива индеx је бројач чворова у претрази у дубину. С је стек чворова, који почиње празан и складишти чворове који су посећени али још увек нису прикључени јако повезаној компоненти. Приметити да ово није класичан стек претраге у дубину, јер се чворови не скидају при враћању претраге уз дрво; они се једино скидају када је нађена цела јако повезана компонента.

Спољашња петља тражи сваки чвор који јос није посећен, и осигурава да чворови који нису достижни из првог чвора су и даље евентуално пређени. Функција стронгцоннецт врши једну претрагу у дубину графа, налазећи све следбенике чвора в, и пријављује све јако повезане компоненте тог подграфа.

Када сваки чвор заврши рекурзију, ако је његов лоwлинк и даље постављен на његов индеx, тада је он корени чвор јако повезане компоненте, формиране од свих чворова изнад у стеку. Алгоритам скида са стека и укључује тренутни чвор, и приказује све ове чворове као јако повезану компоненту.

Примедбе

Сложеност: Тарџанова процедура се позива једном за сваки чвор; за све наредбе разматра чвор највише два пута. Стога је сложеност линеарна по броју грана у графу, тј. $O(|V|+|E|)$ .
Тестирање да ли је w у стеку требало би бити готово у константном времену, на пример тестирањем заставице која за сваки чвор означава да ли је тај чвор у стеку.
Иако нема ничег специјалног у редоследу чворова у свакој јако повезаној компоненти, једно корисно својство алгоритма је да ниједна јако повезана компонента неце бити идентификована пре свог следбеника. Дакле, редослед по коме су јако повезане компоненте идентификоване представља обрнуто тополошко сортирање УАГ, формираног од јако повезаних компоненти.^[2]

Референце

^ Тарјан, Р. Е. (1972), „Дептх-фирст сеарцх анд линеар грапх алгоритхмс”, СИАМ Јоурнал он Цомпутинг, 1 (2): 146—160, дои:10.1137/0201010
^ Харрисон, Паул. „Робуст топологицал сортинг анд Тарјан'с алгоритхм ин Пyтхон”. Приступљено 9. 2. 2011.

Литература

Аспвалл, Бенгт; Пласс, Мицхаел Ф.; Тарјан, Роберт Е. (1979), „А линеар-тиме алгоритхм фор тестинг тхе трутх оф цертаин qуантифиед боолеан формулас”, Информатион Процессинг Леттерс, 8 (3): 121—123, дои:10.1016/0020-0190(79)90002-4 .
Тхомас Х. Цормен; Цхарлес Е. Леисерсон; Роналд L. Ривест; Цлиффорд Стеин (2001). Интродуцтион то Алгоритхмс. Сецонд Едитион. МИТ Пресс анд МцГраw-Хилл. ИСБН 978-0-262-03293-3. Сецтион 22.5, пп. 552-557.}-

Спољашње везе

[1] Тарјан, Р. Е. (1972), „Дептх-фирст сеарцх анд линеар грапх алгоритхмс”, СИАМ Јоурнал он Цомпутинг, 1 (2): 146—160, дои:10.1137/0201010

[2] Харрисон, Паул. „Робуст топологицал сортинг анд Тарјан'с алгоритхм ин Пyтхон”. Приступљено 9. 2. 2011.

[1]

[2]