Topologické řazení

O(V + E)

Topologické řazení uspořádá vrcholy orientovaného acyklického grafu (DAG) tak, že každá hrana vede z dřívějšího vrcholu do pozdějšího — pořadí, ve kterém můžeš plnit úkoly, aniž bys kdy potřeboval nějaký, který ještě nebyl hotový. Kahnův algoritmus ho staví z vstupních stupňů: začni každým vrcholem bez příchozích hran, jeden vypiš a pak odeber jeho odchozí hrany, což může odhalit nové vrcholy se vstupním stupněm nula. Čísla nad uzly sledují zbývající vstupní stupeň každého vrcholu. Běží v O(V + E). Pokud se některé vrcholy nikdy nedostanou na nulu, graf obsahuje cyklus a žádné uspořádání neexistuje. Pohání build systémy, plánovače úkolů i přepočet tabulek.

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

Jak to funguje

  1. Spočítej vstupní stupeň každého vrcholu (příchozí hrany); overlay ho ukazuje.
  2. Zařaď každý vrchol se vstupním stupněm 0 — ty na ničem nezávisí.
  3. Jeden vypiš a sniž vstupní stupeň každého následníka.
  4. Následník, který klesne na 0, se přidá do fronty. Pokud nějaký vrchol zbude, je tam cyklus.

Pseudokód

1topoSort(graph):                    # Kahn — O(V + E)2  indeg[v] ← number of incoming edges3  queue ← all vertices with indeg 04  order ← []5  while queue not empty:6    u ← queue.remove()7    order.append(u)8    for v in successors(u):9      indeg[v] ← indeg[v] − 110      if indeg[v] = 0: queue.add(v)11  if order has every vertex: return order12  else: graph has a cycle