Introduction

Willkommen zurück zur Serie über Graph-Algorithmen! Dieses Mal arbeiten wir mit einem gerichteten Graphen, bei dem jede Kante eine Richtung hat: Eine Kante u -> v bedeutet, dass u vor v kommen muss.

Die Topologische Sortierung ordnet die Knoten eines gerichteten azyklischen Graphen (DAG) in einer Linie an, sodass jede Kante nach vorne zeigt. Sie beantwortet Fragen wie „In welcher Reihenfolge kann ich Kurse belegen, wenn deren Voraussetzungen gegeben sind?“

Der Graph ist gegeben als n (Knoten 0 bis n - 1) und edges, ein flaches Array aus gerichteten Paaren [u0, v0, u1, v1, ...], wobei jedes Paar u -> v bedeutet.

Fangen wir an!