Циклы в генеалогическом древе: как обнаружить и предотвратить некорректные связи?

Проблема циклов в генеалогических данных

Ваша интуиция верна: циклы в генеалогическом древе — это некорректные данные, которые нарушают логику наследования. В реальной жизни человек не может быть предком самому себе. В программировании это означает, что граф родственных связей должен оставаться направленным ациклическим графом (DAG — Directed Acyclic Graph).

Простое рекурсивное сравнение при добавлении каждой связи даёт сложность O(N) в худшем случае, а при N=1000 это ещё терпимо, но если дерево будет расти, производительность упадёт. Лучше использовать поиск в глубину (DFS) с ограничением или алгоритм обнаружения цикла при помощи раскраски вершин.

Эффективное решение: проверка через DFS с цветами

Стандартный алгоритм обнаружения цикла в ориентированном графе — модифицированный DFS с тремя состояниями вершины:

• 0 — WHITE: вершина не посещена
• 1 — GRAY: вершина в текущем стеке рекурсии (возможен цикл)
• 2 — BLACK: вершина обработана, циклов в её поддереве нет

Если при обходе мы встречаем вершину в состоянии GRAY, значит, найден цикл. В вашем случае проверку нужно делать перед фактическим добавлением связи. Предположим, мы добавляем parent → child. Мы временно добавляем child в список детей parent (или в отдельное множество) и запускаем DFS из parent. Если цикл найден — откатываем изменения.

Вот реализация на C++17:

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <functional>

struct Person {
    std::string name;
    Person* father = nullptr;
    Person* mother = nullptr;
    std::vector<Person*> children;
};

class FamilyTree {
    std::vector<Person*> allPersons;
    
    // Проверка на цикл перед добавлением связи
    bool wouldCreateCycle(Person* parent, Person* child) {
        // Временно добавляем связь
        parent->children.push_back(child);
        bool hasCycle = detectCycle();
        // Откатываем
        parent->children.pop_back();
        return hasCycle;
    }
    
    // DFS с раскраской
    bool detectCycle() {
        std::unordered_map<Person*, int> color; // 0=WHITE, 1=GRAY, 2=BLACK
        
        std::function<bool(Person*)> dfs = [&](Person* node) -> bool {
            if (color[node] == 1) return true;  // Цикл!
            if (color[node] == 2) return false; // Уже проверено
            
            color[node] = 1; // GRAY
            for (Person* child : node->children) {
                if (dfs(child)) return true;
            }
            color[node] = 2; // BLACK
            return false;
        };
        
        for (Person* p : allPersons) {
            if (color[p] == 0) {
                if (dfs(p)) return true;
            }
        }
        return false;
    }
    
public:
    void addPerson(const std::string& name) {
        allPersons.push_back(new Person{name});
    }
    
    bool addParentChild(Person* parent, Person* child) {
        if (!parent || !child) return false;
        if (parent == child) {
            std::cerr << "Ошибка: человек не может быть сам себе родителем\n";
            return false;
        }
        
        // Проверка на цикл
        if (wouldCreateCycle(parent, child)) {
            std::cerr << "Ошибка: добавление связи создаст цикл в генеалогическом древе\n";
            return false;
        }
        
        // Безопасное добавление
        parent->children.push_back(child);
        if (child->father == nullptr) child->father = parent;
        else if (child->mother == nullptr) child->mother = parent;
        else {
            std::cerr << "Предупреждение: у ребёнка уже два родителя, связь не добавлена\n";
            parent->children.pop_back();
            return false;
        }
        return true;
    }
    
    ~FamilyTree() {
        for (auto* p : allPersons) delete p;
    }
};

Оптимизация для больших деревьев

Если дерево действительно большое (миллионы узлов), можно использовать LCA (Least Common Ancestor) с предварительным хешированием. Или хранить для каждого узла множество всех предков (set<Person*> ancestors). При добавлении связи проверяем, есть ли parent среди предков child — это O(log N) или O(1) с хеш-таблицей.

Ваш случай (1000 узлов) — DFS с раскраской будет работать мгновенно (менее 1 мс). Главное — не забывайте откатывать временные изменения!

#include <unordered_set>

class TreeWithAncestors {
    std::unordered_map<Person*, std::unordered_set<Person*>> ancestors;
    
public:
    bool addEdge(Person* parent, Person* child) {
        // Проверка: если parent уже в предках child — цикл
        if (ancestors[child].count(parent)) {
            return false; // цикл
        }
        
        // Обновляем предков для child
        ancestors[child].insert(parent);
        for (Person* anc : ancestors[parent]) {
            ancestors[child].insert(anc);
        }
        
        // Обновляем предков для всех потомков child (рекурсивно)
        updateDescendants(child, ancestors[child]);
        return true;
    }
    
private:
    void updateDescendants(Person* node, const std::unordered_set<Person*>& newAncestors) {
        for (Person* desc : node->children) {
            for (Person* anc : newAncestors) {
                ancestors[desc].insert(anc);
            }
            updateDescendants(desc, ancestors[desc]);
        }
    }
};