Косарају–Шариров алгоритам () је алгоритам линеарне временске сложености за проналажење свих јако повезаних компоненти усмереног графа.
Историјат
Алгоритам је 1978. године предложио С. Рао Косарају, али га није објавио. Независно од њега, исти алгоритам је 1981. године открио и објавио Миха Шарир.Aho, A. V., Hopcroft, J. E., Ullman, J. D. Data Structures and Algorithms, Addison-Wesley, 1983.Sharir, M. "A strong-connectivity algorithm and its applications in data flow analysis." Computers & Mathematics with Applications, vol. 7, no. 1, 1981, стр. 67–72. Алгоритам се данас редовно наводи у стандардним уџбеницима из области алгоритама и структура података.Sedgewick, R., Wayne, K. Algorithms, 4th Edition, Addison-Wesley, 2011.
Основни појмови
Усмерени граф састоји се од скупа чворова и скупа усмерених грана . За два чвора и каже се да су јако повезани ако постоји усмерена путања од до и усмерена путања од до . Релација јаке повезаности дели скуп чворова графа на дисјунктне подскупове који се називају јако повезане компоненте (скраћено СЦЦ, од енгл. strongly connected components).
Транспоновани граф добија се обртањем смера свих грана графа . Кључно својство на коме почива алгоритам јесте да граф и његов транспоновани граф имају исте јако повезане компоненте, јер за свака два чвора и постоји пут од до у ако и само ако у постоји пут од до .
Опис алгоритма
Алгоритам се састоји од два DFS пролаза и формирања транспонованог графа, при чему сви кораци имају линеарну сложеност.
Изврши претрагу у дубину (DFS) над оригиналним графом , при чему се сваки чвор, након што су обиђени сви његови суседи, одлаже на стек (то одговара поретку завршетка обраде чвора (енгл. post-order)). Формирај транспоновани граф обртањем свих грана графа . Скидај чворове са стека један по један. За сваки чвор који још увек није посећен, изврши DFS над транспонованим графом почевши од тог чвора. Скуп свих чворова обиђених у једном таквом DFS позиву чини једну јако повезану компоненту.
Интуиција алгоритма може се објаснити посматрањем кондензованог графа, у коме се свака јако повезана компонента посматра као један чвор - тај граф је увек ацикличан. У првом DFS пролазу компоненте се посећују тако да, ако у кондензованом графу постоји пут од једне компоненте до друге, највеће време завршетка чвора у првој компоненти буде веће од највећег времена завршетка чвора у другој. Након транспоновања графа, све гране између компоненти мењају смер. Зато, када се у другом пролазу чворови обрађују опадајућим редоследом времена завршетка, DFS започет у изабраној компоненти не може да досегне друге још необрађене компоненте. Тако сваки DFS позив у другом пролазу проналази тачно једну јако повезану компоненту.
Псеудокод
def kosaraju(G): poseceno = set() redosled = [] # чворови према времену завршетка обраде
def dfs1(u): poseceno.add(u) for v in G.susedi(u): if v not in poseceno: dfs1(v) redosled.append(u)
for u in G.cvorovi(): if u not in poseceno: dfs1(u)
Gt = G.transponuj()
poseceno.clear() komponente = []
def dfs2(u, komponenta): poseceno.add(u) komponenta.append(u) for v in Gt.susedi(u): if v not in poseceno: dfs2(v, komponenta)
for u in reversed(redosled): if u not in poseceno: komponenta = [] dfs2(u, komponenta) komponente.append(komponenta)
return komponente
Пример
thumb|300px|Пример усмереног графа са пет чворова. Чворови 1, 2 и 3 чине једну јако повезану компоненту, док су чворови 4 и 5 сваки за себе засебна компонента.
Посматрајмо усмерени граф са пет чворова и следећим гранама:
1 → 2 2 → 3 3 → 1 3 → 4 4 → 5
Чворови 1, 2 и 3 чине циклус, па су сви међусобно достижни и представљају једну јако повезану компоненту: {1, 2, 3}. Чвор 4 је достижан из те компоненте, али из њега није могуће вратити се назад, па он чини сопствену компоненту {4}. Исто важи и за чвор 5, који чини компоненту {5}. У кондензованом графу овог примера важи {1,2,3} → {4} → {5}: компонента {1,2,3} је изворска (нема улазних грана из других компоненти), а {5} је понорска компонента (нема излазних грана ка другим компонентама).
Ако DFS започне од чвора 1, један могући редослед завршетка обраде је 5, 4, 3, 2, 1. Обрадом чворова у транспонованом графу редоследом обрнутим од редоследа завршетка, дакле почевши од чвора 1, добијају се тачно три компоненте: {1, 2, 3}, {4} и {5}.
Временска и просторна сложеност
Алгоритам захтева два DFS пролаза и формирање транспонованог графа, при чему сваки од ових корака захтева времена. Укупна временска сложеност алгоритма је стога , што је оптимално у стандардном моделу у коме је потребно обрадити улазни граф представљен листама суседства. Просторна сложеност је , због чувања транспонованог графа, стека и скупа посећених чворова.
Недостаци
За разлику од Тарџановог алгоритма, који проналази све јако повезане компоненте у једном DFS пролазу, Косарају–Шариров алгоритам захтева два одвојена DFS пролаза и експлицитно формирање транспонованог графа. Због тога, у односу на приступе који не захтевају чување транспонованог графа, може захтевати додатни простор за његово чување.Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Introduction to Algorithms, 3rd Edition, MIT Press, 2009.
Примена
Алгоритам за налажење јако повезаних компоненти има примену у:
анализи усмерених мрежа, попут веб-графова и мрежа зависности, анализи тока података у компајлерима, анализи достижности и цикличних зависности међу компонентама система, поједностављивању графа кондензацијом сваке јако повезане компоненте у један чвор, чиме се добија ациклички граф погодан за даљу обраду (нпр. за тополошко сортирање).
Види још
Претрага у дубину Тарџанов алгоритам Тополошко сортирање
Референце
Категорија:Алгоритми Категорија:Теорија графова