我们如何在O(V+E)中构造一个算法来计算一条在每个方向上正好穿过G的每条边一次的路径

Question

考虑非有向的连通图G。我们如何在O（V+E）中构造一个算法来计算一条在每个方向上正好穿过G的每条边一次的路径

Answer 1

具有该属性的路径称为欧拉路径。有一个定理说，像这样的路径存在，当且仅当每个节点都有偶数阶，或者正好有两个奇数阶的节点。

在线性时间中有许多构造欧拉路径的算法。一般的想法是（通常）绕着图走，直到得到一个循环，然后通过使用未使用的边来扩展循环，不断增加循环中的边数。你可以在这个链接上阅读更多关于这些算法的信息。