Union-Find

  • Struktura, kterou využívá například Kruskalův algoritmus

  • Reprezentuje komponenty souvislosti grafu a umí na nich provádět následující operace:

    • - vrátí identifikátor komponenty, ve které leží vrchol
    • Pokud pro testovanou hranu platí, že a patří ro různých komponent, pak tyto komponenty spojí do jedné

  • (Obecně: Zjišťuje, do jaké ekvivalenční třídy prvek patří, umí spojit ekvivalenční třídy dohromady)

Implementace pomocí pole

  • Triviální přístup: použijeme pole, které každému vrcholu přiřadí číslo komponenty
  • - přečte číslo v
  • - projde všechny vrcholy jedné komponenty a přiřadí jim číslo té druhé v

Implementace pomocí keříků

  • Reprezentační stromy v Union-Findu budeme nazývat keříky, aby se nám nepletly se stromy v Kruskalově algoritmu
  • Každou komponentu (strom), vznikající během Kruskala, budeme reprezentovat speciálním stromem (keříkem) orientovaným směrem do kořene
  • Vrcholy keříků odpovídají vrcholům příslušné komponenty
  • Každý vrchol si pamatuje pouze svého otce
  • Kořeny keříků mají (nemají otce)

../Attachments/Pasted image 20230125210944.png

  • - vystoupá postupně do kořene a vrátí ID kořene (tedy komponenty), trvá hloubka
  • - mělčí keřík napojí pod kořen hlubšího, případně zvýší hloubku +1 pokud jsou stejné, trvá
    • (je nutné si u každého pamatovat jeho hloubku, né ji vždy počítat)

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25