Генеалогический алгоритм: Как программно найти всех родителей (дедушек и бабушек) для конкретного parentId, используя связи в графе?

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

## Структура данных

Предположим, что связи хранятся в виде массива объектов:

[
{ «id»: 1, «parentId»: null },
{ «id»: 2, «parentId»: 1 },
{ «id»: 3, «parentId»: 1 },
{ «id»: 4, «parentId»: 2 }
]

## Рекурсивный подход (DFS)

Самый интуитивный способ — рекурсивный обход вверх по дереву:

javascript
function findAllAncestors(nodes, targetId) {
const nodeMap = new Map(nodes.map(n => [n.id, n]));
const ancestors = [];

function traverse(id) {
const node = nodeMap.get(id);
if (!node || node.parentId === null) return;
const parent = nodeMap.get(node.parentId);
if (parent) {
ancestors.push(parent);
traverse(parent.id);
}
}

traverse(targetId);
return ancestors;
}

Эта функция поднимается по цепочке parentId до корня, собирая всех предков.

## Итеративный подход (BFS)

Для больших деревьев рекурсия может вызвать переполнение стека. Итеративный вариант безопаснее:

javascript
function findAllAncestorsBFS(nodes, targetId) {
const nodeMap = new Map(nodes.map(n => [n.id, n]));
const ancestors = [];
const queue = [targetId];

while (queue.length > 0) {
const currentId = queue.shift();
const node = nodeMap.get(currentId);
if (!node || node.parentId === null) continue;
const parent = nodeMap.get(node.parentId);
if (parent) {
ancestors.push(parent);
queue.push(parent.id);
}
}

return ancestors;
}

## Обработка графов с несколькими родителями (DAG)

Если узел может иметь несколько родителей (не дерево, а DAG), структуру нужно изменить:

javascript
// nodes: [{ id, parentIds: [1, 2] }]
function findAllAncestorsDAG(nodes, targetId) {
const nodeMap = new Map(nodes.map(n => [n.id, n]));
const visited = new Set();
const ancestors = [];
const stack = [targetId];

while (stack.length > 0) {
const currentId = stack.pop();
if (visited.has(currentId)) continue;
visited.add(currentId);
const node = nodeMap.get(currentId);
if (!node) continue;
for (const parentId of (node.parentIds || [])) {
const parent = nodeMap.get(parentId);
if (parent && !visited.has(parentId)) {
ancestors.push(parent);
stack.push(parentId);
}
}
}

return ancestors;
}

## SQL-подход (рекурсивный CTE)

Если данные хранятся в реляционной БД, используйте рекурсивный Common Table Expression:

sql
WITH RECURSIVE ancestors AS (
SELECT * FROM nodes WHERE id = :targetId
UNION ALL
SELECT n.* FROM nodes n
JOIN ancestors a ON n.id = a.parent_id
)
SELECT * FROM ancestors WHERE id != :targetId;

## Рекомендации

— Всегда проверяйте на наличие циклов в графе (используйте Set для visited).
— Для глубоких деревьев предпочитайте итеративный подход рекурсивному.
— Индексируйте поле parentId в базе данных для ускорения запросов.
— Кэшируйте результаты, если дерево статично и запросы повторяются.

Выбор алгоритма зависит от структуры данных: простое дерево, DAG или реляционная таблица.