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