Изменить характеристики GIF

Если я правильно понял ваш вопрос, то новый ребро (u, v) будет вставлен только в том случае, если раньше не было пути от v до u (т. е. если (u, v) не создает цикл). Таким образом, ваш график всегда является DAG (направленный ациклический граф). Использование алгоритма Тарьяна для обнаружения сильно связанных компонентов ( http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm ) звучит как перебор в этом случае. Перед вставкой (u, v) все, что вам нужно проверить, это то, существует ли направленный путь от v до u, что можно сделать с помощью простой BFS / DFS.

Таким образом, самый простой способ сделать это (n = | V |, m = | E |):

• Вставка (u, v): проверьте, существует ли путь от v до u (BFS / DFS). Сложность времени: O (m)
• Удаление краев: просто удалите их из графика. Сложность времени: O (1)

Хотя вставка (u, v) занимает O (m) время в худшем случае, вероятно, довольно быстро в вашей ситуации. Когда вы делаете BFS / DFS, начиная с v, чтобы проверить, достижимо ли u, вы только посещаете вершины, которые достижимы с v. Я бы предположил, что в вашей настройке граф довольно разрежен и что число вершин, доступных другому, не так высокий.

Однако, если вы хотите улучшить теоретическое время работы, вот несколько советов (в основном это показывает, что это будет непросто). Предположим, мы стремимся к тестированию в течение O (1) времени, существует ли направленный путь от v до u. Ключевым в этом контексте является транзитивное замыкание DAG (т. Е. Графа, содержащего ребро (u, v) тогда и только тогда, когда есть направленный путь от u до v в DAG). К сожалению, сохранение транзитивного замыкания в динамическом режиме кажется не таким простым. Есть несколько статей, посвященных этой проблеме, и все документы, которые я нашел, были документами STOC или FOCS, что свидетельствует о том, что они очень вовлечены. Самый новый (и самый быстрый) результат, который я нашел, приведен в статье «Динамическое транзитивное закрытие с помощью динамической матрицы инверсии» Санковского ( http://dl.acm.org/citation.cfm?id=1033207 ).

Даже если вы готовы понять один из этих динамических транзитивных алгоритмов закрытия (или даже хотите его реализовать), они не будут давать вам ускорение по следующей причине. Эти алгоритмы предназначены для ситуации, где у вас много запросов на подключение (которые затем могут быть выполнены в O (1) раз) и только несколько изменений в графике. Цель состоит в том, чтобы сделать эти изменения дешевле, чем перерасчет транзитивного закрытия. Однако это обновление все еще медленнее, чем одна проверка подключения. Таким образом, если вам нужно сделать обновление для каждого запроса на подключение, лучше использовать простой подход, упомянутый выше.

Итак, почему я упоминаю этот подход поддержания транзитивного закрытия, если он не подходит для вашего потребности? Ну, это показывает, что поиск алгоритма, использующего только время запроса O (1), вероятно, не приведет вас к решению быстрее простого с использованием BFS / DFS. То, что вы можете попробовать, - это получить время запроса, которое быстрее, чем O (m), но хуже, чем O (1), а обновления также быстрее, чем O (m). Это очень интересная проблема, но это звучит для меня как очень амбициозная цель (так что, возможно, не трать слишком много времени на ее достижение).