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
01.index = 002. 03./*04. * Spousti tarjanuv algoritmus05. * @param g graf, v nemz budou hledany silne komponenty06. * @return seznam komponent 07. */08.List executeTarjan(Graph g) 09. Stack s = {}10. List scc = {} //seznam silnych komponent11. for Node node in g12. if (v.index is undefined)13. tarjanAlgorithm(node, scc, s) 14. 15. return scc16. 17./*18. * Tarjanuv algoritmus19. * @param node zpracovavany uzel20. * @param SCC seznam komponent (seznamu uzlu v komponentach)21. * @param s zasobnik22. */23.procedure tarjanAlgorithm(Node node, List scc, Stack s)24. v.index = index25. v.lowlink = index26. index++27. s.push(node) //pridej na zasobnik28. for each Node n in Adj(node) do //pro vsechny potomky29. if n.index == -1 //pokud jeste nebyl uzel objeven30. tarjanAlgorithm(n, scc, s, index) //prohledej31. node.lowlink = min(node.lowlink, n.lowlink) //uprav lowlink otce32. else if stack.contains(n) //pokud komponenta nebyla jiz uzavrena33. node.lowlink = min(node.lowlink, n.index)34. 35. if node.lowlink == node.index //pokud jsme v koreni komponenty36. Node n = null37. List component //seznam uzlu dane komponenty38. do39. n = stack.pop() //vyber uzel ze zasobniku40. component.add(n) //pridej ho do komponenty41. while(n != v) //dokud nejsme v koreni42. scc.add(component) //komponentu pridej do seznamu komponent