Какую структуру данных лучше всего использовать для отношений потомства?

Question

Должна быть стандартная структура данных для хранения, например, информации о разведении собак, генетическом скрещивании растений и сложных человеческих отношениях.

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

Я ожидаю, что кто-то уже занимался этим раньше. Какие ресурсы я должен изучить?

Answer 1

Я думаю, что у вас есть простая реляционная база данных, где основным отношением является "child_of", "direct_descendant" и т. Д.

Конечно, конкретная структура данных здесь является ациклической, и вы можете захотеть сделать транзитивные запросы (потомок потомка ...), которые обычно не поддерживаются стандартными механизмами SQL.

Так что, если вы хотите сделать это в памяти, вы можете использовать ориентированный ациклический граф (DAG).

Answer 2

Пахнет DAG . Если направленный и ациклический слишком ограничен, вы можете взглянуть на структуры данных теории графов .

Используя графики для абстрактных задач, вершины представляют сущности, а ребра представляют отношения.