Algoritmy.net > Grafy > Tarjanův algoritmus
Tarjanův algoritmus
Tarjanův algoritmus (Tarjan's algorithm) je grafový algoritmus sloužící k vyhledávání silných komponent orientovaného grafu. Silná komponenta je maximální množina uzlů orientovaného grafu taková, že mezi každými dvěma uzly existuje sled.
Princip
Tarjanův algoritmus vychází z prohledávání do hloubky. Vrcholy se při prohledávání indexují dle pořadí svého nalezení. Při návratu z rekurze se každému vrcholu přiřadí uzel s nejnižším indexem na jaký lze dosáhnout. Všechny vrcholy, které mají totožný cílový uzel (index), jsou ve stejné komponentě.
Složitost
Tarjanův algoritmus má stejně jako prohledávání do hloubky asymptotickou složitost .
Kód
/*
* Tarjanuv algoritmus
* @param node zpracovavany uzel
* @param SCC seznam komponent (seznamu uzlu v komponentach)
* @param s zasobnik
* @param index index slouzici k cislovani uzlu
* @return seznam komponent
*/
List tarjanAlgorithm(Node node, List scc, Stack s, int index)
v.index = index
v.lowlink = index
index++
s.push(node) //pridej na zasobnik
for each Node n in Adj(node) do //pro vsechny sousedy
if n.index == -1 //pokud jeste nebyl uzel objeven
tarjanAlgorithm(n, scc, s, index) //prohledej
node.lowlink = min(node.lowlink, n.lowlink) //uprav lowlink otce
else if stack.contains(n)
node.lowlink = min(node.lowlink, n.index)
if node.lowlink == node.index //pokud jsme v koreni komponenty
Node n = null
List component //seznam uzlu dane komponenty
do
n = stack.pop() //vyber uzel ze zasobniku
component.add(n) //pridej ho do komponenty
while(n != v) //dokud nejsme v koreni
scc.add(component) //komponentu pridej do seznamu komponent
return scc //vrat seznam komponent
