проверка Directed Graph для мостов

Question

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

Answer 1

Я только что нашел лучшее или более простое решение для этого ..
выберите любой узел, запустите простой dfs и проверьте, посещен ли каждый узел, затем поверните все ребра и, начиная с того же узла, проверьте, можете ли вы посетитьвсе узлы снова, если нет, то он обязательно содержит мост.

Answer 2

В случае, если график направлен аналогично мостам для неориентированного графа, мы будем называть ребро сильным мостом , если его удаление увеличивает число сильно связанных компонент графа.Чтобы проверить, имеет ли ориентированный граф сильные мосты, вам нужно запустить алгоритм, подробно изложенный в статье: Джузеппе Ф. Итальяно, Луиджи Лаура, Федерико Сантарони: Поиск сильных мостов и точек сильного сочленения за линейное время .Теор.Вычи.Sci.447: 74-84 (2012) http://dx.doi.org/10.1016/j.tcs.2011.11.011

Answer 3

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

Запустите на своем графике алгоритм сильно связанных компонентов Тарьяна. если результат отличается от того, что на вашем графике есть мост.