Ciclos em software genealógico: como funciona por baixo dos panos em C++

Introdução: por que não existem loops temporais em uma árvore genealógica

Imagine: você está escrevendo um programa para construir uma árvore genealógica. Tudo vai bem, até que o usuário adiciona uma relação: "João — pai de Pedro, Pedro — pai de João". O programa trava, a recursão entra em loop infinito, e o usuário recebe um Stack Overflow no sentido literal da palavra. Situação familiar? Essa questão é uma das mais populares no Stack Overflow (milhares de visualizações), e não é à toa.

Neste artigo, vamos analisar como funcionam os ciclos em árvores genealógicas por baixo dos panos. Mostrarei como detectar e processar essas situações em C++, para que seu family tree software não falhe, mas funcione como um relógio. Você aprenderá não apenas a teoria dos grafos, mas também obterá código pronto que pode ser adaptado imediatamente ao seu projeto.

\n

Importante: O artigo foi escrito para o site educacional pythonlib.ru, mas o código é totalmente em C++ — um ótimo exemplo de como os algoritmos transcendem as fronteiras das linguagens.

\n

Por que ciclos são um problema para software genealógico?

Uma árvore genealógica é um grafo direcionado (directed graph). Cada nó é uma pessoa, cada aresta é uma relação (pai → filho). Na vida real, ciclos não podem existir: ninguém pode ser seu próprio ancestral. Mas, no programa, o usuário pode acidentalmente criar essa relação:

\n
• Alice é mãe de Bob
\n
• Bob é pai de Alice
\n

Se seu algoritmo de travessia (por exemplo, para exibir todos os ancestrais) não verificar ciclos, ele ficará iterando infinitamente entre Alice → Bob → Alice → Bob... Isso leva a:

\n
• Congelamento do programa
\n
• Estouro de pilha (stack overflow)
\n
• Consumo infinito de memória
\n

Portanto, a detecção de ciclos em grafos é uma tarefa básica para qualquer aplicação genealógica séria.

Estrutura de dados: como armazenar uma árvore genealógica em C++

Antes de falar sobre algoritmos, precisamos definir a representação. Sugiro usar uma lista de adjacência (adjacency list) — é eficiente e intuitiva.

#include <iostream>\n#include <unordered_map>\n#include <vector>\n#include <string>\n#include <stack>\n\nclass FamilyTree {\nprivate:\n    // Cada pessoa é um nó com um nome único (ID)\n    // Arestas: pai -> filho\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        // Se a criança ainda não está no grafo — adiciona lista vazia\n        if (parentToChild.find(child) == parentToChild.end()) {\n            parentToChild[child] = {};\n        }\n    }\n    \n    // ... métodos para travessia\n};\n

Aqui, cada chave é o nome de uma pessoa, e o valor é a lista de seus filhos. Esta é uma estrutura de dados para árvore genealógica mínima, mas funcional. Agora vamos ao principal.

Como detectar um ciclo: algoritmo de busca em profundidade (DFS)

A maneira padrão de encontrar um ciclo em um grafo direcionado é a busca em profundidade (DFS) modificada. A ideia é simples: marcamos os vértices com três cores:

\n
• Branco (0) — não visitado
\n
• Cinza (1) — em processo de travessia (na pilha de recursão atual)
\n
• Preto (2) — completamente processado
\n

Se durante a DFS encontrarmos um vértice com cor cinza — é um ciclo. Vamos implementar isso em 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