Union-Find in C#

Problem

Ein Kunde, drei Profile

Der Shop hat 200.000 Kundenprofile. Derselbe Kunde hat sich dreimal angemeldet: einmal mit der Telefonnummer, einmal mit der Firmen-E-Mail, einmal über die App. Sie bekommt drei Newsletter, ihre Treuepunkte sind auf drei Konten verteilt, und der Bericht sagt, du hättest mehr Kunden, als du hast.

Die Regel ist einfach: Zwei Profile mit derselben E-Mail oder derselben Telefonnummer sind ein Kunde. Aber sie ist ansteckend. Wenn Profil a mit b eine Telefonnummer teilt und b mit c eine E-Mail, dann sind a, b und c ein Kunde, obwohl a und c nichts gemeinsam haben.

Wie findest du alle Gruppen, ohne jedes Profil mit jedem anderen zu vergleichen?

Die Idee

Die erste Idee: ein Gruppenlabel

Jedes Profil trägt ein Label: die Nummer seiner Gruppe. Am Anfang ist jedes Profil seine eigene Gruppe. Stellt sich heraus, dass zwei Profile verbunden sind, bekommt die ganze Gruppe des zweiten das Label des ersten.

class Relabel
{
    private readonly int[] label;

    public int Count { get; private set; }

    public Relabel(int n)
    {
        label = new int[n];
        for (int i = 0; i < n; i++) label[i] = i;
        Count = n;
    }

    public int Find(int x) => label[x];

    public bool Union(int a, int b)
    {
        int from = label[b];
        int to = label[a];
        if (from == to) return false;
        for (int i = 0; i < label.Length; i++)
        {
            if (label[i] == from) label[i] = to;
        }
        Count--;
        return true;
    }
}

Das Programm geht die Profile durch und merkt sich für jeden Kontakt, welches Profil ihn zuerst hatte. Sieht es den Kontakt wieder, verschmilzt es die beiden Profile:

string[][] profiles =
[
    ["mara@post.de", "0151 100200"],
    ["0151 100200", "m.weber@firma.de"],
    ["peter@post.de"],
    ["m.weber@firma.de"],
    ["0152 300400", "peter@post.de"],
    ["nico@post.de"],
    ["0152 300400"],
    ["nico@post.de", "0153 500600"],
    ["mara@post.de", "0152 300400"],
];
var accounts = new Relabel(profiles.Length);
var owner = new Dictionary<string, int>();
for (int p = 0; p < profiles.Length; p++)
{
    foreach (string contact in profiles[p])
    {
        if (owner.TryGetValue(contact, out int first))
        {
            accounts.Union(first, p);
        }
        else
        {
            owner[contact] = p;
        }
    }
}
Console.WriteLine("Gruppen: " + accounts.Count);
var main = Enumerable.Range(0, profiles.Length).Select(accounts.Find);
Console.WriteLine("Haupt: " + string.Join(" ", main));

Gruppen: 2
Haupt: 2 2 2 2 2 5 2 5 2

Es funktioniert, aber jede Verschmelzung läuft über alle Profile, um zu finden, welche umbenannt werden müssen. Bei n Profilen und etwa n Verschmelzungen sind das etwa n² Blicke: zig Milliarden bei 200.000 Profilen.

Die Idee

Ein Wald aus Eltern

Statt dass jedes Profil das Gruppenlabel trägt, zeigt jedes Profil auf einen Elternteil: ein anderes Profil der Gruppe. Die Gruppe ist ein Baum, und das Profil, das auf sich selbst zeigt, ist die Wurzel: das Hauptprofil der Gruppe.

find(x) steigt die Eltern hinauf, bis es eine Wurzel erreicht. Zwei Profile sind in einer Gruppe, wenn find für beide dieselbe Wurzel gibt.
union(a, b) findet die Wurzeln beider und hängt eine unter die andere. Es berührt eine Zelle des Arrays, egal wie groß die Gruppe ist.

Für sich allein kann der Wald zu einer langen Kette werden, und dann ist find langsam. Darum gibt es zwei Verbesserungen, und zusammen sind sie Union-Find:

Vereinigung nach Größe. Jede Wurzel weiß, wie viele Profile ihr Baum hat. Der kleinere Baum kommt unter den größeren, damit die Tiefe langsam wächst.
Pfadkompression. Hat find die Wurzel erreicht, geht es den Pfad noch einmal ab und hängt jedes Profil darauf direkt an die Wurzel. Das nächste find für sie ist ein Schritt.

Sieh es dir an

Eine Verschmelzung von innen

class UnionFind
{
    private readonly int[] parent;
    private readonly int[] size;

    public int Count { get; private set; }

    public UnionFind(int n)
    {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++)
        {
            parent[i] = i;
            size[i] = 1;
        }
        Count = n;
    }

    public int Find(int x)
    {
        int root = x;
        while (parent[root] != root) root = parent[root];
        while (parent[x] != root)
        {
            int above = parent[x];
            parent[x] = root;
            x = above;
        }
        return root;
    }

    public bool Union(int a, int b)
    {
        int ra = Find(a);
        int rb = Find(b);
        if (ra == rb) return false;
        if (size[ra] < size[rb]) (ra, rb) = (rb, ra);
        parent[rb] = ra;
        size[ra] += size[rb];
        Count--;
        return true;
    }
}

Union gibt false zurück, wenn die Profile schon in einer Gruppe sind: Dann ändert sich nichts, und Count bleibt.

Dasselbe Programm wie oben, mit UnionFind statt Relabel:

string[][] profiles =
[
    ["mara@post.de", "0151 100200"],
    ["0151 100200", "m.weber@firma.de"],
    ["peter@post.de"],
    ["m.weber@firma.de"],
    ["0152 300400", "peter@post.de"],
    ["nico@post.de"],
    ["0152 300400"],
    ["nico@post.de", "0153 500600"],
    ["mara@post.de", "0152 300400"],
];
var accounts = new UnionFind(profiles.Length);
var owner = new Dictionary<string, int>();
for (int p = 0; p < profiles.Length; p++)
{
    foreach (string contact in profiles[p])
    {
        if (owner.TryGetValue(contact, out int first))
        {
            accounts.Union(first, p);
        }
        else
        {
            owner[contact] = p;
        }
    }
}
Console.WriteLine("Gruppen: " + accounts.Count);
var main = Enumerable.Range(0, profiles.Length).Select(accounts.Find);
Console.WriteLine("Haupt: " + string.Join(" ", main));

Gruppen: 2
Haupt: 0 0 0 0 0 5 0 5 0

class UnionFind
{
    private readonly int[] parent;
    private readonly int[] size;

    public int Count { get; private set; }

    public UnionFind(int n)
    {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++)
        {
            parent[i] = i;
            size[i] = 1;
        }
        Count = n;
    }

    public int Find(int x)
    {
        int root = x;
        while (parent[root] != root) root = parent[root];
        while (parent[x] != root)
        {
            int above = parent[x];
            parent[x] = root;
            x = above;
        }
        return root;
    }

    public bool Union(int a, int b)
    {
        int ra = Find(a);
        int rb = Find(b);
        if (ra == rb) return false;
        if (size[ra] < size[rb]) (ra, rb) = (rb, ra);
        parent[rb] = ra;
        size[ra] += size[rb];
        Count--;
        return true;
    }
}

Schritt für Schritt, in Worten

Neun Kundenprofile, jedes ist seine eigene Gruppe: parent[i] = i, jedes Profil ist eine Wurzel. Gruppen: 9.
Profil 1 hat die Telefonnummer von 0: Union(0, 1). Die Wurzeln sind verschieden, also wird 1 unter 0 gehängt. Dann hat 3 die E-Mail von 1: Find(1) steigt zu 0, und 3 kommt auch unter 0.
Genauso bei den anderen: 4 unter 2 (gemeinsame E-Mail), 6 unter 2 (gemeinsame Telefonnummer), 7 unter 5. Ein union ändert eine Zelle des Arrays: den Elternteil einer Wurzel.
Profil 8 hat die E-Mail von 0: 8 kommt unter 0. Die Gruppe von 0 hat jetzt vier Profile.
8 hat auch die Telefonnummer von 4. Find(4) erreicht 2, Find(8) erreicht 0. Der Baum von 2 ist kleiner (3 gegen 4), darum kommt seine Wurzel unter 0: eine Zelle ändert sich, drei Profile wechseln die Gruppe.
Am Ende ruft das Programm Find für jedes Profil auf. Find(4) steigt 4 → 2 → 0 hinauf und hängt dann 4 direkt an 0: Pfadkompression. Genauso bei 6.
Zwei Gruppen, die Hauptprofile sind 0 und 5. Der Baum ist flach: Das nächste Find(4) ist ein Schritt.

Die beiden Gruppen sind dieselben wie mit Labels, nur die Zahlen unterscheiden sich: Hier ist das Hauptprofil die Wurzel, bei Labels ist es das Label, das übrig geblieben ist.

Probier es aus

Sag die Ausgabe voraus

Sechs Profile und sechs Verbindungen. Nach jedem union notiert das Programm die Zahl der Gruppen:

var uf = new UnionFind(6);
int[][] links = [[0, 1], [1, 2], [0, 2], [3, 4], [4, 5], [2, 3]];
var counts = new List<int>();
foreach (int[] link in links)
{
    uf.Union(link[0], link[1]);
    counts.Add(uf.Count);
}
Console.WriteLine("[" + string.Join(", ", counts) + "]");

Antwort

[1, 1, 1, 1, 1, 1]

[5, 4, 3, 2, 1, 0]

[5, 4, 4, 3, 2, 1]

Die Idee

Das rekursive find

Die Kompression wird oft als Rekursion geschrieben: find auf dem Elternteil gibt die Wurzel, und das Profil wird an sie gehängt. Jedes Profil auf dem Pfad tut auf dem Rückweg dasselbe.

public int Find(int x)
{
    if (parent[x] != x) parent[x] = Find(parent[x]);
    return parent[x];
}

Versuch es selbst:

public int Find(int x)
{
    if (parent[x] != x) parent[x] = ;
    return parent[x];
}

Mit der Vereinigung nach Größe sind die Bäume niedrig: höchstens 17 Ebenen für 200.000 Profile (log₂ 200.000 ≈ 17,6). Die Rekursion ist also sicher.

Genauer, für Neugierige

Ohne die Vereinigung nach Größe kann ein Baum zu einer Kette aus n Profilen werden, und das rekursive find macht n verschachtelte Aufrufe, die übereinander gestapelt werden, wie in der Lektion „Rekursion“. In C# beendet ein Stapelüberlauf den ganzen Prozess: StackOverflowException lässt sich nicht abfangen. Die Schleife aus der Lektion hat dieses Problem bei keiner Form des Baums.

Die Idee

Was es kostet

Lass die drei Wege laufen. Es gibt n Profile und n zufällige Verbindungen „diese zwei teilen einen Kontakt“. Gezählt wird:

mit Labels: jeder Blick auf das Label eines Profils beim Umbenennen;
beim einfachen Wald und bei Union-Find: jeder Schritt von find, einschließlich des Blicks auf die Wurzel selbst.

Die ganze Gruppe umbenennen O(n²)
Elternwald, ohne Verbesserungen O(n²)
Union-Find: Kompression und Größe O(n)

Algorithmus	n = 10	n = 1.000	n = 10.000	n = 100.000
Die ganze Gruppe umbenennen	90	843.000	≈ 84.300.000	≈ 8.430.000.000
Elternwald, ohne Verbesserungen	30	25.641	2.102.613	≈ 210.261.300
Union-Find: Kompression und Größe	30	3.295	33.355	334.195

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

class UnionFind
{
    private readonly int[] parent;
    private readonly int[] size;

    public int Count { get; private set; }

    public UnionFind(int n)
    {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++)
        {
            parent[i] = i;
            size[i] = 1;
        }
        Count = n;
    }

    public int Find(int x)
    {
        int root = x;
        while (parent[root] != root) root = parent[root];
        while (parent[x] != root)
        {
            int above = parent[x];
            parent[x] = root;
            x = above;
        }
        return root;
    }

    public bool Union(int a, int b)
    {
        int ra = Find(a);
        int rb = Find(b);
        if (ra == rb) return false;
        if (size[ra] < size[rb]) (ra, rb) = (rb, ra);
        parent[rb] = ra;
        size[ra] += size[rb];
        Count--;
        return true;
    }
}

Bei 1000 Profilen brauchen die Labels 843.000 Blicke, der einfache Wald 25.641 Schritte und Union-Find 3295. Bei 10.000 braucht der einfache Wald schon 2.102.613 Schritte: Seine Bäume werden zu langen Ketten. Union-Find braucht 33.355, etwa 3,3 Schritte pro Verbindung, und bei 100.000 Profilen 334.195: pro Verbindung dasselbe.

Das sind amortisierte Kosten (siehe amortisierte Komplexität): Ein find kann lang sein, aber danach ist der Pfad flach, und die nächsten sind kurz. Insgesamt kostet jede Operation fast O(1).

Genauer, für Neugierige

Genauer: Mit Vereinigung nach Größe (oder nach Rang, siehe unten) und Pfadkompression kosten m Operationen auf n Elementen O(m · α(n)). α ist die inverse Ackermann-Funktion. Sie wächst so langsam, dass sie für jedes n, das ins Universum passt, höchstens 4 ist. Darum sagt man in der Praxis „fast konstant“. Der Beweis stammt von Tarjan (1975) und ist nicht kurz.

Statt der Größe kannst du einen Rang führen: eine obere Schranke für die Höhe des Baums. Die Wurzel mit dem kleineren Rang kommt unter die andere, und ein Rang wächst nur, wenn die Ränge gleich sind. Die Kosten sind dieselben. Die Größe ist handlicher, weil sie auch „wie viele Profile sind in der Gruppe“ beantwortet.

Probier es aus

Finde den Fehler

Ein Kollege hat das union geschrieben. Die Zahl der Gruppen ist 2, aber es gibt drei verschiedene Hauptprofile:

public bool Union(int a, int b)
{
    int ra = Find(a);
    int rb = Find(b);
    if (ra == rb) return false;
    if (size[ra] < size[rb]) (ra, rb) = (rb, ra);
    parent[b] = ra;
    size[ra] += size[rb];
    Count--;
    return true;
}

string[][] profiles =
[
    ["mara@post.de", "0151 100200"],
    ["0151 100200", "m.weber@firma.de"],
    ["peter@post.de"],
    ["m.weber@firma.de"],
    ["0152 300400", "peter@post.de"],
    ["nico@post.de"],
    ["0152 300400"],
    ["nico@post.de", "0153 500600"],
    ["mara@post.de", "0152 300400"],
];
var accounts = new UnionFind(profiles.Length);
var owner = new Dictionary<string, int>();
for (int p = 0; p < profiles.Length; p++)
{
    foreach (string contact in profiles[p])
    {
        if (owner.TryGetValue(contact, out int first))
        {
            accounts.Union(first, p);
        }
        else
        {
            owner[contact] = p;
        }
    }
}
Console.WriteLine("Gruppen: " + accounts.Count);
var main = Enumerable.Range(0, profiles.Length).Select(accounts.Find);
Console.WriteLine("Haupt: " + string.Join(" ", main));

Gruppen: 2
Haupt: 0 0 2 0 2 5 2 5 0

In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Die Idee

Wo noch

Union-Find beantwortet eine Frage: Sind diese beiden in einer Gruppe, wenn Gruppen nur wachsen. Dasselbe gilt für:

Liefergebiete: Lager und Straßen dazwischen. Zwei Lager sind in einem Gebiet, wenn es eine Route gibt, auch über andere Lager;
ein Computernetz: welche Rechner sich nach jedem neuen Kabel erreichen;
den Algorithmus von Kruskal für das billigste Straßennetz, den du im Modul Graphen (algo-graphs) siehst. Dort sagt Union-Find, ob eine neue Straße einen Zyklus schließt.

Eine Grenze: Union-Find trennt nicht. Stellt sich eine gemeinsame Nummer als Büronummer heraus und hat sie zwei verschiedene Kunden verschmolzen, lässt sich das union nicht rückgängig machen. Darum werden die Verbindungen getrennt gespeichert, und die Gruppen werden neu gebaut, wenn eine Verbindung wegfällt. Darum benutzt man eine Nummer, die in Hunderten Profilen vorkommt, meist gar nicht zum Verschmelzen.

Übung

Liefergebiete

Löse es in deinem Editor.

Gebiete. Es gibt 10 Lager (0 … 9) und Straßen dazwischen: 0-1, 1-2, 3-4, 5-6, 6-7, 7-5, 8-9. Füge der Klasse zwei Methoden hinzu: Connected(a, b), die sagt, ob zwei Lager in einem Gebiet sind, und SizeOf(x), die zurückgibt, wie viele Lager im Gebiet von x sind. Gib die Zahl der Gebiete aus, ob 0 und 2 und ob 2 und 3 in einem Gebiet sind und wie viele Lager im Gebiet von 5 sind. Dann eröffne eine neue Straße 2-3 und gib die Zahl der Gebiete noch einmal aus und ob 0 und 4 in einem Gebiet sind:

Gebiete: 4
0 und 2: ja
2 und 3: nein
Gebiet von 5: 3 Lager
Neue Straße 2-3. Gebiete: 3
0 und 4: ja

Weitere Aufgaben

Gruppen nach Namen. Gib jede Gruppe von Profilen als Liste aus: das Hauptprofil und alle Profile darunter.
Die größte Gruppe. Führe die größte Gruppengröße beim Verschmelzen mit, ohne am Ende alle Wurzeln abzugehen.
Vereinigung nach Rang. Ersetze die Größe durch den Rang und vergleiche die Zahl der find-Schritte mit denen in Bench.

Test

Teste dich

1. Die Profile a und b teilen eine E-Mail, b und c teilen eine Telefonnummer, und d teilt nichts mit niemandem. Wie viele Kunden sind das?2: a, b und c sind ein Kunde, d ist ein anderer3: a und c teilen keinen Kontakt4: Jedes Profil ist für sich

2. Was macht union, wenn die beiden Profile schon in einer Gruppe sind?Es hängt die Wurzel unter sich selbstNichts: find gibt dieselbe Wurzel, und die Zahl der Gruppen bleibtEs senkt die Zahl der Gruppen um eins

3. Warum kommt die Wurzel des kleineren Baums unter die Wurzel des größeren und nicht umgekehrt?Damit das älteste Profil das Hauptprofil bleibtDamit die Tiefe nur wächst, wenn die Größen gleich sind, und nie über log₂ n steigtDas ist egal, es sieht nur schöner aus

4. Zwei Profile wurden über eine gemeinsame Telefonnummer verschmolzen, und es stellt sich heraus, dass es eine Büronummer ist. Wie trennst du sie wieder?Mit einem umgekehrten unionDie Gruppen aus den Verbindungen neu bauen, ohne die falscheDas Handy aus dem Array der Eltern entfernen

Union-Find

Cookies