Algorithmen und Datenstrukturen · Senior · Frage 47 von 75
Warum kann Union-Find keine Zyklen in einem gerichteten Graphen erkennen?
- 1Es kann nur Knoten speichern, die Zahlen sind
- 2Ihm geht bei gerichteten Graphen der Speicher aus
- 3Es ignoriert die Richtung, eine Raute wirkt also wie ein Zyklus
Antwort zeigen
Richtige Antwort: Es ignoriert die Richtung, eine Raute wirkt also wie ein Zyklus
Erklärung
Union-Find verfolgt Zusammenhang, nicht Richtung. In einem DAG würden zwei Wege zum selben Knoten (eine Raute) bereits verbundene Knoten verbinden, was wie ein Zyklus aussieht, aber keiner ist.