Ciclos en el software genealógico: cómo funciona bajo el capó en C++

Introducción: por qué no hay bucles temporales en un árbol genealógico

Imagine: está escribiendo un programa para construir un árbol familiar. Todo va bien hasta que el usuario añade una relación: «Iván es padre de Pedro, Pedro es padre de Iván». El programa se congela, la recursión se vuelve infinita y el usuario obtiene un Stack Overflow en el sentido literal de la palabra. ¿Le suena familiar? Esta pregunta es una de las más populares en Stack Overflow (miles de visitas), y no es para menos.

En este artículo, analizaremos cómo funcionan los ciclos en el árbol genealógico bajo el capó. Le mostraré cómo detectar y manejar estas situaciones en C++ para que su family tree software no se caiga, sino que funcione como un reloj. No solo aprenderá teoría de grafos, sino que también obtendrá código listo para adaptar a su proyecto.

\n

Importante: El artículo está escrito para el sitio educativo pythonlib.ru, pero el código es completamente en C++: un excelente ejemplo de cómo los algoritmos cruzan las fronteras de los lenguajes.

\n

¿Por qué los ciclos son un problema para el software genealógico?

Un árbol familiar es un grafo dirigido (directed graph). Cada nodo es una persona, cada arista es una relación (padre → hijo). En la vida real no pueden existir ciclos: nadie puede ser su propio antepasado. Pero en el programa, el usuario podría crear accidentalmente una relación así:

\n
• Alicia es madre de Bob
\n
• Bob es padre de Alicia
\n

Si su algoritmo de recorrido (por ejemplo, para mostrar todos los antepasados) no verifica ciclos, iterará infinitamente sobre Alicia → Bob → Alicia → Bob... Esto provoca:

\n
• Congelación del programa
\n
• Desbordamiento de pila (stack overflow)
\n
• Consumo infinito de memoria
\n

Por lo tanto, la detección de ciclos en grafos es una tarea básica para cualquier aplicación genealógica seria.

Estructura de datos: cómo almacenar un árbol familiar en C++

Antes de hablar de algoritmos, debemos definir la representación. Propongo usar una lista de adyacencia (adjacency list): es eficiente y clara.

#include <iostream>\n#include <unordered_map>\n#include <vector>\n#include <string>\n#include <stack>\n\nclass FamilyTree {\nprivate:\n    // Cada persona es un nodo con un nombre único (ID)\n    // Aristas: padre -> hijo\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        // Si el hijo aún no está en el grafo, agregamos una lista vacía\n        if (parentToChild.find(child) == parentToChild.end()) {\n            parentToChild[child] = {};\n        }\n    }\n    \n    // ... métodos para recorrido\n};\n

Aquí cada clave es el nombre de una persona, y el valor es la lista de sus hijos. Esta es una estructura de datos para árbol genealógico mínima pero funcional. Ahora pasemos a lo principal.

Cómo detectar un ciclo: algoritmo de búsqueda en profundidad (DFS)

La forma estándar de encontrar un ciclo en un grafo dirigido es una búsqueda en profundidad (DFS) modificada. La idea es simple: marcamos los vértices con tres colores:

\n
• Blanco (0) — no visitado
\n
• Gris (1) — en proceso de recorrido (en la pila de recursión actual)
\n
• Negro (2) — completamente procesado
\n

Si durante el DFS encontramos un vértice de color gris, es un ciclo. Implementemos esto en C++.

#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