Fleury算法的时间复杂度
您能帮我找出 Fleury' 算法（用于获取欧拉电路）的时间复杂度吗？
Could you please help me find out the time complexity of the Fleury' algorithm (which is used to get the Eulerian circuit)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
在您指定如何识别桥边缘之前，Fleury 的算法并不是真正完整的。 Tarjan 给出了用于识别所有桥梁的线性时间算法（参见 http://en.wikipedia.org /wiki/Bridge_(graph_theory) ），因此在每个删除的边之后重新运行 Tarjan 算法的简单实现将是 O(E^2)。可能有更好的方法来重新计算桥集，但也有更好的 O(E) 算法。 （参见http://www.algorithmist.com/index.php/Euler_tour#Fleury .27s_algorithm；不是我的网站:))
Fleury's algorithm isn't really complete until you specify how the bridge edges are identified. Tarjan gave a linear-time algorithm for identifying all bridges (see http://en.wikipedia.org/wiki/Bridge_(graph_theory) ), so a naive implementation that reran Tarjan's algorithm after each deleted edge would be O(E^2). There are probably better ways to recompute the set of bridges, but there is also a better O(E) algorithm. (See http://www.algorithmist.com/index.php/Euler_tour#Fleury.27s_algorithm ; not my site :))
这里：
你可以读到它是 O(E)，线性边缘计数。
Here:
http://roticv.rantx.com/book/Eulerianpathandcircuit.pdf
you can read among other things, that it is O(E), linear edge count.
Fleury 算法涉及以下步骤：
确保图有 0 或 2 个奇数顶点。
如果有 0 个奇数顶点，则从任意位置开始。如果有 2 个奇数顶点，则从其中之一开始。
一次跟随一个边。如果您可以在桥式和非桥式之间进行选择，请始终选择非桥式。
当你用完边缘时停止。
如果通过 Tarjan 算法找到了桥，并且将这些桥存储在邻接矩阵中，那么我们不需要每次都运行 Tarjan 算法来检查一条边是否是桥。我们可以在 O(1) 时间内检查所有其他桥接查询。因此，Flury 的算法时间复杂度可以降低到 O(V+E) {因为这是 DFS}，但该方法需要 O(V2) 额外空间来存储桥。
Fleury algorithm involves following steps :
Make sure the graph has either 0 or 2 odd vertices.
If there are 0 odd vertices, start anywhere. If there are 2 odd vertices, start at one of them.
Follow edges one at a time. If you have a choice between a bridge and a non-bridge, always choose the non-bridge.
Stop when you run out of edges.
If bridges are found out by Tarjan's algorithm and these bridges are stored in an adjacency matrix then we need not run tarjan's algorithm every time to check whether an edge is a bridge or not. We can check it in O(1) time for all other bridge queries. Thus Flury's algorithm time complexity can be reduced to O(V+E) {as this is a DFS} but this method needs O(V2) extra space to store bridges.