Detekce cyklu

O(V + E)

Cyklus je cesta, která se vrátí tam, kde začala, aniž by použila hranu dvakrát. K jeho detekci v neorientovaném grafu spusť DFS a pamatuj si rodiče každého vrcholu ve stromu prohledávání. Při procházení sousedů vrcholu — pokud narazíš na takový, který už byl navštíven a není to bezprostřední rodič — tato hrana uzavírá cyklus. Pokud DFS projde všechny komponenty bez takové zpětné hrany, graf je acyklický (les). Běží v O(V + E) a je základem detekce uváznutí, kontroly koster i otázky „je to strom?“.

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. DFS z libovolného vrcholu, zaznamenávej rodiče každého vrcholu.
  2. Pro každého souseda zanoř se do těch nenavštívených.
  3. Pokud je soused už navštívený a není to rodič, zpětná hrana uzavírá cyklus.
  4. Pokud DFS vyčerpá každou komponentu bez zpětné hrany, graf je acyklický.

Pseudokód

1hasCycle(graph):                     # O(V + E)2  dfs(u, parent):3    mark u visited4    for v in neighbours(u):5      if v not visited:6        if dfs(v, u): return true7      else if v ≠ parent:8        return true                   # back edge closes a cycle9    return false10  run dfs from every unvisited vertex