Существует ли структура данных для групп обеспечения доступности баз данных, которая поддерживает эффективное редактирование?

Question

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

Спасибо!

Answer 1

Вы можете сохранить структуру данных о транзитивном замыкании графа . Затем проверка того, вызывает ли добавление ребра циклы, выполняется за постоянное время; если вы хотите добавить ребро (i, j), проверьте, существует ли уже путь от j до i. Однако обновление структуры данных в целом может быть более затратным (см., Например, La Poutré и van Leeuwen ).