Algorithmen und Datenstrukturen · Middle · Frage 33 von 75
Wie erkennt man mit DFS einen Zyklus in einem gerichteten Graphen?
- 1Jede Kante zu einem schon besuchten Knoten bedeutet einen Zyklus
- 2Ein Zyklus existiert, wenn ein Knoten mehr als eine ausgehende Kante hat
- 3Den aktuellen DFS-Pfad verfolgen; eine Kante zurück in ihn ist ein Zyklus
Antwort zeigen
Richtige Antwort: Den aktuellen DFS-Pfad verfolgen; eine Kante zurück in ihn ist ein Zyklus
Erklärung
Nutze drei Zustände: unbesucht, in Arbeit (auf dem Stack) und fertig. Nur eine Kante zu einem Knoten „in Arbeit“ ist eine Rückwärtskante. Eine Kante zu einem „fertigen“ Knoten ist in Ordnung: nur ein weiterer Weg zum selben Ort.