Algorithmen und Datenstrukturen · Middle · Frage 34 von 75
Was unterstützt eine Union-Find-Struktur (Disjoint Set)?
- 1Mengen verbinden und prüfen, ob zwei Elemente in einer Menge sind
- 2Elemente sortieren und das k-kleinste finden
- 3Schlüssel-Wert-Paare mit schnellen Bereichsabfragen speichern
Antwort zeigen
Richtige Antwort: Mengen verbinden und prüfen, ob zwei Elemente in einer Menge sind
Erklärung
union(a, b) verbindet zwei Gruppen, und find(a) liefert den Repräsentanten einer Gruppe. Mit Pfadkompression und Union by Rank sind beide nahezu O(1). Typische Einsätze: Zusammenhangskomponenten, Kruskals MST, „sind diese Konten dieselbe Person?“