Временная сложность алгоритма Флери

Question

Не могли бы вы помочь мне выяснить временную сложность алгоритма Флери (который используется для получения эйлерова схемы)?

Answer 1

Алгоритм Флери на самом деле не завершен, пока вы не укажете, как определяются края моста. Тарьян дал алгоритм линейного времени для идентификации всех мостов (см. http://en.wikipedia.org/wiki/Bridge_(graph_theory)), поэтому наивная реализация, которая перезапускает алгоритм Тарьяна после каждого удаленного ребра, будет O (E ^ 2). Вероятно, существуют более эффективные способы пересчета набора мостов, но есть также лучший алгоритм O (E). (См. http://www.algorithmist.com/index.php/Euler_tour#Fleury.27s_algorithm; не мой сайт:))

Answer 2

Здесь: http://roticv.rantx.com/book/Eulerianpathandcircuit.pdf Вы можете прочитать среди прочего, что это O (E), линейный счетчик ребер.

Answer 3

алгоритм Флери включает в себя следующие шаги:

1. Убедитесь, что в графе 0 или 2 нечетных вершины.

2. Если существует 0 нечетных вершин, начните с любого места. Если есть 2 нечетные вершины, начните с одной из них.

3. Следуйте по краям по одному. Если у вас есть выбор между мостом и без моста, всегда выбирайте без моста.

4. Остановитесь, когда у вас кончатся края.

Если мосты обнаруживаются алгоритмом Тарьяна, и эти мосты хранятся в матрице смежности, то нам не нужно каждый раз запускать алгоритм Тарьяна, чтобы проверить, является ли ребро мостом или нет. Мы можем проверить это за O (1) время для всех других запросов моста. Таким образом, временная сложность алгоритма Флери может быть уменьшена до O (V + E) {так как это DFS}, но для этого метода требуется дополнительное пространство O (V2) для хранения мостов.