Как определить, приводит ли добавление ребра к ориентированному графу к циклу?

Если я правильно понял ваш вопрос, то новое ребро (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 (м)
• Удаление ребер: просто удалите их с графика. Сложность времени: 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). Это очень интересная проблема, но мне кажется, что это очень амбициозная цель (так что, возможно, не тратьте слишком много времени на ее достижение ...).

Как предположил Марк, можно использовать структуру данных, в которой хранятся подключенные узлы. Лучше всего использовать логическую матрицу |V|x|V|. Значения можно инициализировать с помощью алгоритма Флойда – Уоршалла. Это сделано в O(|V|^3).

Пусть T(i) будет набором вершин, у которых есть путь к вершине i, и F(j) набором вершин, где существует путь от вершины j. Первый - это истина в i строке, а второй - истина в j столбце.

Добавление ребра (i,j) - простая операция. Если i и j не были подключены ранее, то для каждого a из T(i) и каждого b из F(j) установите для элемента матрицы (a,b) значение true. Но операция стоит недешево. В худшем случае это O(|V|^2). Это в случае направленной линии, и добавление ребра от конца к начальной вершине соединяет все вершины со всеми остальными вершинами.

Удаление ребра (i,j) не так уж и просто, но в худшем случае не более затратная операция :-) Если после удаления ребра есть путь от i к j, то ничего не меняется. То, что проверено Дейкстрой, меньше O(|V|^2). Вершины, которые больше не связаны, (a,b):

• a in T(i) - i - T(j),
• b in F(j) + j

Только T(j) изменяется при удалении кромки (i,j), поэтому его необходимо пересчитать. Это делается с помощью любого вида обхода графа (BFS, DFS), проходя в направлении, противоположном направлению ребра от вершины j. Это делается менее чем за O(|V|^2). Поскольку установка элемента матрицы в худшем случае снова равна O(|V|^2), эта операция имеет такую ​​же сложность наихудшего случая, как и добавление ребра.

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

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

https://stackoverflow.com/a/261621/831850

Итак, если у нас есть отсортированный список узлов:

1, 2, 3, ..., x, ..., z, ...
Such that each node is waiting for nodes to its left.

Скажем, мы хотим добавить ребро от x-> z. Хорошо, что вроде как тормозить. Таким образом, мы можем переместить узел в x в положение z + 1, что зафиксирует сортировку i, если ни один из узлов (x, z) не имеет ребра к узлу в x.