McGill Metro-System: Union-Find, Kruskal & Trie Tutorial

Einleitung: Das McGill Metro-Problem und warum es relevant ist

Stell dir vor, du musst in nur 10 Minuten vom unteren Campus zur Stewart Biology Building kommen – ein Albtraum für jeden COMP 251 Studenten. Genau dieses Problem greift die finale Abgabe auf: Mit einem effizienten Metrosystem sollen Studierende schneller zwischen Gebäuden pendeln können. Dabei kommen zentrale Algorithmen und Datenstrukturen zum Einsatz, die auch in der realen Welt – von Google Maps bis zur Routenplanung in Spielen wie Genshin Impact – verwendet werden.

In diesem Tutorial lernst du, wie du die Aufgabenstellungen DisjointSet, maxPassengers, bestMetroSystem und Passengersuche mit Trie systematisch angehst. Wir verzichten auf fertige Lösungen, geben dir aber das Rüstzeug, um deinen eigenen Code zu schreiben und im Code Review zu glänzen.

1. Grundlagen: Union-Find mit Pfadkompression und Union-by-Size

Die Basis für viele Graphalgorithmen ist die disjunkte Mengenverwaltung (Union-Find). Deine naive Implementierung muss um zwei Optimierungen erweitert werden:

Pfadkompression (find): Bei jeder Suche nach der Wurzel eines Knotens werden alle besuchten Knoten direkt an die Wurzel gehängt. Das reduziert die Tiefe des Baums.
Union-by-Size oder Union-by-Rank: Beim Vereinigen zweier Mengen wird der kleinere Baum an den größeren gehängt. So bleibt die Höhe logarithmisch.

Ohne diese Optimierungen wird dein Code für die großen Testfälle zu langsam – der STM (Simulated Transit of McGill) erwartet nahezu konstante Laufzeit pro Operation.

public int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // Pfadkompression
    }
    return parent[x];
}

public void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX == rootY) return;
    if (size[rootX] < size[rootY]) {
        parent[rootX] = rootY;
        size[rootY] += size[rootX];
    } else {
        parent[rootY] = rootX;
        size[rootX] += size[rootY];
    }
}

2. Maximale Passagierzahl zwischen zwei Gebäuden

Die Methode maxPassengers(BuildingID start, BuildingID end) soll die maximale Anzahl Personen ermitteln, die direkt von start nach end reisen können. Wichtig: Die tracks sind gerichtet? Nein, in dieser Aufgabe sind sie ungerichtet – du kannst also in beide Richtungen fahren. Die Kapazität einer Verbindung ist das Minimum aus den occupants der beiden Gebäude und der capacity des Tracks.

Da der Graph spärlich ist (wenige Kanten im Verhältnis zur Knotenzahl), bietet sich eine Adjazenzliste an. Du kannst für jedes Gebäude eine Liste der Nachbarn mit Kapazität speichern. Die Suche nach dem maximalen Durchfluss ist hier trivial: Es gibt nur eine mögliche direkte Verbindung. Falls keine Kante existiert, ist das Ergebnis 0.

Beispiel: Building A (100 occupants) und Building B (50 occupants) sind durch einen Track mit capacity 30 verbunden. Das Minimum ist 30 → maxPassengers = 30.

3. Das beste Metrosystem mit Kruskals Algorithmus

Die bestMetroSystem() Methode ist der Kern der Abgabe. Du suchst einen maximal spannenden Baum (Maximum Spanning Tree) bezogen auf die „Güte“ einer Kante. Die Güte ist definiert als:

goodness = floor( min(start.occupants, end.occupants, track.capacity) / track.cost )

Das erinnert an die Cost-Performance-Optimierung in der echten Welt: Wie viele Passagiere bekommst du pro investiertem Dollar? Ähnlich wie bei der Auswahl des besten Internet-Tarifs oder der effizientesten KI-Modells (z. B. bei der Token-Nutzung von ChatGPT) suchst du die maximale Effizienz.

Implementiere den Algorithmus wie folgt:

Berechne für jeden Track die goodness.
Sortiere alle Tracks absteigend nach goodness (oder verwende einen Max-Heap).
Initialisiere Union-Find mit allen Gebäuden.
Iteriere über die sortierten Tracks: Wenn die beiden Gebäude des Tracks in unterschiedlichen Mengen sind, füge den Track zur Lösung hinzu und vereinige die Mengen.
Stoppe, wenn du n-1 Kanten ausgewählt hast (n = Anzahl Gebäude).

Die Laufzeit wird durch das Sortieren dominiert: O(m log m) mit m = Anzahl Tracks.

4. Passagierverwaltung mit einem Trie (Präfixbaum)

Die Methoden addPassenger(String name) und searchForPassengers(String firstLetters) verlangen eine effiziente Suche nach Namenspräfixen. Ein Trie (Präfixbaum) ist ideal: Jeder Knoten repräsentiert einen Buchstaben, und ein Wortende wird markiert.

Wichtige Details aus der Aufgabenstellung:

Groß-/Kleinschreibung ignorieren: Speichere alle Namen in Kleinbuchstaben, aber gib sie mit großem Anfangsbuchstaben zurück.
Doppelte Namen: Gib nur einen Eintrag zurück – du kannst entweder ein Set verwenden oder im Trie ein Flag setzen.
Alphabetische Reihenfolge: Beim Durchlaufen des Tries musst du die Kinder in lexikografischer Reihenfolge besuchen.

Der Trie wird auch in Autovervollständigungsfunktionen von Apps wie WhatsApp oder in der Suchfunktion von KI-Assistenten (z. B. Alexa) verwendet. Hier ein einfaches Grundgerüst:

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd;
}

Füge beim Einfügen jeden Buchstaben als Knoten hinzu. Bei der Suche navigiere entlang des Präfixes und sammle dann alle Wörter ab dem letzten Knoten (DFS mit alphabetischer Reihenfolge).

5. Testen und häufige Fehler vermeiden

Da ihr nur 50 Einreichungen habt, ist lokales Testen entscheidend. Nutzt die bereitgestellten Beispieltests und erstellt eigene. Achtet auf:

Union-Find: Vergesst nicht, Pfadkompression und Union-by-Size zu implementieren – sonst läuft der Code bei großen Datenmengen in die Knie.
maxPassengers: Denkt daran, dass die Kapazität das Minimum aus drei Werten ist. Ein häufiger Fehler ist, nur die Track-Kapazität zu betrachten.
bestMetroSystem: Stellt sicher, dass der Graph zusammenhängend ist (wie in der Aufgabenstellung garantiert). Die Güteformel verwendet floor – ganzzahlige Division ist wichtig.
Trie: Case-Insensitivity und doppelte Namen korrekt behandeln. Testet mit Namen wie „alex“, „Alex“, „ALEX“ – alle sollten denselben Eintrag liefern.

6. Zeitkomplexitäten und Begründungen für das Code Review

Im Code Review müsst ihr jede Entscheidung erklären können. Hier die erwarteten Komplexitäten:

DisjointSet.find: nahezu O(α(n)) (inverse Ackermann-Funktion) mit Pfadkompression.
DisjointSet.union: ebenfalls O(α(n)).
maxPassengers: O(1) bei Adjazenzliste (direkter Lookup).
bestMetroSystem: O(m log m) für Sortieren + O(m α(n)) für Union-Find.
addPassenger: O(L) mit L = Länge des Namens.
searchForPassengers: O(P + S) mit P = Länge des Präfixes, S = Anzahl der gefundenen Namen (jeder Buchstabe wird einmal besucht).

Begründet eure Datenstrukturwahl: Warum Adjazenzliste statt Matrix? Weil der Graph spärlich ist. Warum Trie statt HashSet für Präfixsuche? Weil der Trie O(P) für die Suche braucht, während HashSet lineare Suche über alle Namen erfordern würde.

Fazit

Mit diesen Erklärungen und Code-Snippets bist du gut gerüstet, um die COMP 251 Final Assignment zu meistern. Denk daran: Keine KI-Unterstützung – der Lernerfolg kommt durch eigenes Implementieren und Verstehen. Viel Erfolg beim Bauen des effizientesten Metro-Systems von McGill!