Как обнаружить и предотвратить циклы в генеалогическом дереве на C++?

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

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

Лучшее решение — проверять наличие пути от ребенка к родителю перед добавлением связи. Если такой путь существует, значит, добавление создаст цикл.

Алгоритм обнаружения цикла

Используем поиск в глубину (DFS) или поиск в ширину (BFS) от узла-ребенка вверх по родителям. Если мы достигнем узла-родителя, то цикл есть. Для эффективности можно кешировать результаты проверок (мемоизация), но для простоты начнем с базового варианта.

Пример реализации на C++17

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <queue>

struct Person {
    std::string name;
    std::vector<Person*> parents;
    std::vector<Person*> children;
    
    Person(const std::string& n) : name(n) {}
};

// Проверка: есть ли путь от 'start' к 'target' по ссылкам parents?
bool hasPathToParent(Person* start, Person* target) {
    if (!start || !target) return false;
    if (start == target) return true;
    
    std::unordered_set<Person*> visited;
    std::queue<Person*> q;
    q.push(start);
    visited.insert(start);
    
    while (!q.empty()) {
        Person* current = q.front();
        q.pop();
        
        for (Person* parent : current->parents) {
            if (parent == target) return true;
            if (visited.find(parent) == visited.end()) {
                visited.insert(parent);
                q.push(parent);
            }
        }
    }
    return false;
}

// Безопасное добавление связи
bool addParentChildSafe(Person* parent, Person* child) {
    if (!parent || !child) return false;
    
    // 1. Проверка на цикл: существует ли путь от parent к child через родителей?
    // Если да, то child — предок parent, добавление создаст цикл.
    if (hasPathToParent(parent, child)) {
        std::cerr << "Ошибка: добавление связи " << parent->name 
                  << " -> " << child->name << " создаст цикл!" << std::endl;
        return false;
    }
    
    // 2. Если цикла нет, добавляем связь
    parent->children.push_back(child);
    child->parents.push_back(parent);
    return true;
}

// Пример использования
int main() {
    Person* A = new Person("Alice");
    Person* B = new Person("Bob");
    Person* C = new Person("Charlie");
    
    addParentChildSafe(A, B); // OK
    addParentChildSafe(B, C); // OK
    addParentChildSafe(C, A); // Ошибка: цикл!
    
    // Очистка памяти (в реальном проекте используйте умные указатели)
    delete A; delete B; delete C;
    return 0;
}

Оптимизация и альтернативы

• Мемоизация: сохраняйте результаты проверки для пар (start, target), чтобы не пересчитывать каждый раз.
• Использование std::shared_ptr: замените сырые указатели на умные, чтобы избежать утечек памяти.
• Глобальный граф: если у вас много узлов, храните список всех вершин и проверяйте наличие цикла во всем графе после каждого добавления (алгоритм topological sort).
• Альтернативный подход: вместо хранения двунаправленных ссылок храните только родителей и вычисляйте детей на лету (но это медленнее).

Почему это работает?

Генеалогическое дерево — это DAG, где ребра направлены от предков к потомкам. Если мы добавляем ребро от parent к child, то должны убедиться, что child не является предком parent. BFS/DFS по родителям от parent проверяет именно это. Если мы нашли child среди предков parent, то ребро замыкает цикл.

В вашем примере с A→B, B→C, C→A: при попытке добавить C→A, BFS от C по родителям найдет B, затем от B найдет A, и обнаружит, что A — предок C. Связь будет отклонена.

#include <unordered_map>
#include <queue>
#include <vector>

bool isAcyclic(const std::vector<Person*>& allPersons) {
    std::unordered_map<Person*, int> inDegree;
    for (auto* p : allPersons) {
        inDegree[p] = p->parents.size();
    }
    
    std::queue<Person*> q;
    for (auto* p : allPersons) {
        if (inDegree[p] == 0) q.push(p);
    }
    
    int visitedCount = 0;
    while (!q.empty()) {
        Person* current = q.front();
        q.pop();
        visitedCount++;
        for (Person* child : current->children) {
            if (--inDegree[child] == 0) q.push(child);
        }
    }
    return visitedCount == allPersons.size();
}