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 $O(\\vert U \\vert + \\vert H \\vert)$ .

Kód

Pseudocode

    index = 0
 
    /*
     * Spousti tarjanuv algoritmus
     * @param g graf, v nemz budou hledany silne komponenty
     * @return seznam komponent 
     */
    List executeTarjan(Graph g)             
        Stack s = {}
        List scc = {} //seznam silnych komponent
        for Node node in g
            if (v.index is undefined)
                tarjanAlgorithm(node, scc, s)    
        
        return scc
 
    /*
     * Tarjanuv algoritmus
     * @param node zpracovavany uzel
     * @param SCC seznam komponent (seznamu uzlu v komponentach)
     * @param s zasobnik
     */
    procedure tarjanAlgorithm(Node node, List scc, Stack s)
        v.index = index
        v.lowlink = index
        index++
        s.push(node) //pridej na zasobnik
        for each Node n in Adj(node) do //pro vsechny potomky
            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) //pokud komponenta nebyla jiz uzavrena
                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

Princip

Složitost

Kód

Doporučujeme