Schleifen in Genealogie-Software: Wie es unter der Haube mit C++ funktioniert

Einleitung: Warum es in Stammbäumen keine Zeitreisen gibt

Stellen Sie sich vor: Sie schreiben ein Programm zur Erstellung eines Stammbaums. Alles läuft hervorragend, bis der Benutzer eine Verbindung hinzufügt: „Iwan ist der Vater von Peter, Peter ist der Vater von Iwan“. Das Programm friert ein, die Rekursion läuft ins Unendliche, und der Benutzer erhält im wahrsten Sinne des Wortes einen Stack Overflow. Kommt Ihnen das bekannt vor? Diese Frage ist eine der beliebtesten auf Stack Overflow (tausende Aufrufe), und das aus gutem Grund.

In diesem Artikel analysieren wir, wie Schleifen im Stammbaum unter der Haube funktionieren. Ich zeige Ihnen, wie Sie solche Situationen in C++ erkennen und verarbeiten, damit Ihre family tree software nicht abstürzt, sondern wie am Schnürchen läuft. Sie lernen nicht nur die Graphentheorie, sondern erhalten auch fertigen Code, den Sie sofort an Ihr Projekt anpassen können.

\n

Wichtig: Der Artikel wurde für die Bildungswebsite pythonlib.ru geschrieben, aber der Code ist vollständig in C++ – ein hervorragendes Beispiel dafür, wie Algorithmen Sprachgrenzen überschreiten.

\n

Warum sind Schleifen ein Problem für Genealogie-Software?

Ein Stammbaum ist ein gerichteter Graph (directed graph). Jeder Knoten ist eine Person, jede Kante eine Beziehung (Elternteil → Kind). Im echten Leben kann es keine Schleifen geben: Niemand kann sein eigener Vorfahre sein. Aber im Programm kann ein Benutzer versehentlich eine solche Verbindung herstellen:

\n
• Alice ist die Mutter von Bob
\n
• Bob ist der Vater von Alice
\n

Wenn Ihr Durchlaufalgorithmus (z. B. zur Anzeige aller Vorfahren) keine Schleifen prüft, wird er endlos Alice → Bob → Alice → Bob durchlaufen... Dies führt zu:

\n
• Einfrieren des Programms
\n
• Stapelüberlauf (stack overflow)
\n
• Unendlichem Speicherverbrauch
\n

Daher ist die Zyklenerkennung im Graphen eine grundlegende Aufgabe für jede ernsthafte genealogische Anwendung.

Datenstruktur: Wie man einen Stammbaum in C++ speichert

Bevor wir über Algorithmen sprechen, müssen wir uns für eine Darstellung entscheiden. Ich schlage die Verwendung einer Adjazenzliste (adjacency list) vor – das ist effizient und anschaulich.

#include <iostream>\n#include <unordered_map>\n#include <vector>\n#include <string>\n#include <stack>\n\nclass FamilyTree {\nprivate:\n    // Jede Person ist ein Knoten mit einem eindeutigen Namen (ID)\n    // Kanten: Elternteil -> Kind\n    std::unordered_map<std::string, std::vector<std::string>> parentToChild;\n    \npublic:\n    void addRelation(const std::string& parent, const std::string& child) {\n        parentToChild[parent].push_back(child);\n        // Wenn das Kind noch nicht im Graphen ist – leere Liste hinzufügen\n        if (parentToChild.find(child) == parentToChild.end()) {\n            parentToChild[child] = {};\n        }\n    }\n    \n    // ... Methoden zum Durchlaufen\n};\n

Hier ist jeder Schlüssel der Name einer Person, der Wert eine Liste seiner Kinder. Dies ist eine minimale, aber funktionale Datenstruktur für eine Ahnentafel. Kommen wir nun zum Wesentlichen.

Wie man einen Zyklus erkennt: Tiefensuche (DFS)-Algorithmus

Die Standardmethode, um einen Zyklus in einem gerichteten Graphen zu finden, ist eine modifizierte Tiefensuche (DFS). Die Idee ist einfach: Wir markieren Knoten mit drei Farben:

\n
• Weiß (0) – nicht besucht
\n
• Grau (1) – im Durchlauf (im aktuellen Rekursionsstack)
\n
• Schwarz (2) – vollständig verarbeitet
\n

Wenn wir während der DFS auf einen Knoten mit grauer Farbe stoßen – das ist ein Zyklus. Lassen Sie uns dies in C++ implementieren.

#include <unordered_map>\n#include <string>\n#include <vector>\n\nenum class Color { WHITE, GRAY, BLACK };\n\nclass CycleDetector {\nprivate:\n    std::unordered_map<std::string, std::vector<std::string>>& graph;\n    std::unordered_map<std::string, Color> color;\n    \n    bool