Komponenty silné souvislosti

O(V + E)

V orientovaném grafu je komponenta silné souvislosti maximální množina vrcholů, kde každý vrchol dosáhne každého jiného po hranách. Kosarajův algoritmus je najde všechny dvěma průchody. Nejdřív spustí DFS přes celý graf a každý vrchol vloží na zásobník ve chvíli, kdy dokončí (takže ten, co dokončí poslední, skončí navrchu). Pak obrátí každou hranu a spustí DFS znovu, tentokrát bere startovní vrcholy ze zásobníku v tomto pořadí — každý strom, který druhé DFS vytvoří, je přesně jedna SCC. Obrácení hran je ten chytrý trik: omezí druhé hledání na jedinou komponentu. Běží v O(V + E). SCC odhalují cyklické závislosti, zhušťují graf na DAG komponent a stojí za 2-SAT. Každá komponenta je zobrazena vlastní barvou.

Orientovaný graf
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Průchod 1: DFS grafu, zaznamenej každý vrchol, když dokončí.
  2. Obrať každou hranu (transponuj graf).
  3. Průchod 2: DFS transpozice, ber vrcholy v obráceném pořadí dokončení.
  4. Každý strom, který druhý průchod vytvoří, je jedna komponenta silné souvislosti.

Pseudokód

1kosaraju(graph):                    # O(V + E)2  pass 1: DFS the graph, pushing each3          vertex onto a stack when it finishes4  transpose the graph (reverse every edge)5  pass 2: pop vertices in that order; each6          DFS on the transpose marks one SCC7  vertices coloured alike form a component