Komponenty souvislosti

O(V + E)

Komponenta souvislosti je maximální množina vrcholů, které se navzájem dosáhnou po hranách; graf se rozpadá na jednu či více disjunktních komponent. Najdeš je tak, že zvolíš libovolný nenavštívený vrchol a záplavově se rozšíříš ven pomocí BFS (nebo DFS), přičemž každý dosažený vrchol dostane stejnou barvu — to je jedna komponenta. Opakuj z dalšího nenavštíveného vrcholu novou barvou, dokud nějaké zbývají. Celý průchod se dotkne každého vrcholu i hrany jednou, takže běží v O(V + E). Odpovídá na otázku „je graf v jednom kuse?“ a stojí za shlukováním, řešením bludišť i dosažitelností v síti.

Klik do prázdna = vrchol · klik na 2 vrcholy = hrana · táhni = posuňStart: A
Vstupní graf
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Vyber nenavštívený vrchol a začni novou barvu komponenty.
  2. Rozšiř se ven (BFS/DFS) a obarvi každý dosažený vrchol touto barvou.
  3. Když se záplava zastaví, komponenta je hotová.
  4. Přejdi na další nenavštívený vrchol s novou barvou, dokud nejsou všechny obarvené.

Pseudokód

1connectedComponents(graph):         # O(V + E)2  k ← 03  for each vertex s:4    if s is unvisited:5      BFS/DFS from s, tagging every6      reachable vertex with colour k  # one component7      k ← k + 18  return k                            # number of components