Klasse UnionFind<T>

java.lang.Object
TelNetApplication.UnionFind<T>
public class UnionFind<T> extends Object
Klasse für Union-Find-Strukturen. Unterstützt die effiziente Verwaltung einer Partionierung einer Menge (disjunkte Zerlegung in Teilmengen). Union-Find-Struktur mit Pfadkompression und Union-by-Rank. Im Durchschnitt haben unionByRank und findWithCompression praktisch eine Laufzeit von O(1).
Seit:
24.01.2025

  • Konstruktorübersicht

    Konstruktoren
    Konstruktor
    Beschreibung
    UnionFind(Set<T> s)
    Legt eine neue Union-Find-Struktur mit allen 1-elementigen Teilmengen von s an.

  • Methodenübersicht

    Modifizierer und Typ
    Methode
    Beschreibung
    T
    find(T e)
    Liefert den Repräsentanten der Teilmenge zurück, zu der e gehört.
    static void
    main(String[] args)
     
    void
    print()
    Ausgabe der Union-Find-Struktur zu Testzwecken.
    int
    size()
    Liefert die Anzahl der Teilmengen in der Partitionierung zurück.
    void
    union(T e1, T e2)
    Vereinigt die beiden Teilmengen, die e1 bzw. e2 enthalten.

    Von Klasse geerbte Methoden java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Konstruktordetails

    • UnionFind

      public UnionFind(Set<T> s)
      Legt eine neue Union-Find-Struktur mit allen 1-elementigen Teilmengen von s an.
      Parameter:
      s - Menge von Elementen, für die eine Partionierung verwaltet werden soll.

  • Methodendetails

    • find

      public T find(T e)
      Liefert den Repräsentanten der Teilmenge zurück, zu der e gehört. Pfadkompression wird angewendet.
      Parameter:
      e - Element
      Gibt zurück:
      Repräsentant der Teilmenge, zu der e gehört.
      Löst aus:
      IllegalArgumentException - falls e nicht in der Partionierung vorkommt.

    • union

      public void union(T e1, T e2)
      Vereinigt die beiden Teilmengen, die e1 bzw. e2 enthalten. Die Vereinigung wird nur durchgeführt, falls die beiden Mengen unterschiedlich sind. Es wird union-by-rank durchgeführt.
      Parameter:
      e1 - Element.
      e2 - Element.
      Löst aus:
      IllegalArgumentException - falls e1 und e2 keine Elemente der Union-Find-Struktur sind.

    • print

      public void print()
      Ausgabe der Union-Find-Struktur zu Testzwecken.

    • size

      public int size()
      Liefert die Anzahl der Teilmengen in der Partitionierung zurück.
      Gibt zurück:
      Anzahl der Teilmengen.

    • main

      public static void main(String[] args)