algorithm - 如何在有向图中找到所有欧拉路径

Question

我有一个有向图，我想找到所有现有的欧拉路径(在我的图中我实际上知道那些将是电路)。

我做了一些研究，所以我可以使用 Hierholzer 的算法，如下所示:http://stones333.blogspot.co.uk/2013/11/find-eulerian-path-in-directed-graph.html从给定节点找到一条路径，但我认为该算法只返回一条路径。

我解决这个问题的想法是拥有一个算法，该算法将返回从给定节点开始的所有现有欧拉路径/电路。然后我将对所有节点运行该算法并获得结果。这将具有 n^2 或 n^3 的复杂性，这很好。

所以我的问题是是否有一种算法可以从给定节点找到有向图中的所有欧拉路径/电路？或者也许有人知道我的问题的另一种解决方案。

编辑:在 Gassa 发表评论后，我认为使用 Euler 路径的解决方案对我的问题来说可能有点矫枉过正。问题如下:对于给定的 n，我们创建一对整数，其总和 <= n。对于这些对，找到连接所有对的所有路径，使得前一对的第二个值等于下一对的第一个值(如多米诺骨牌)。

示例:n = 2，则可用对 = {(0,0), (0,1),(1,0),(1,1),(2,0),(0,2)} .其中一个有效链 = (0,0)=>(0,1)=>(1,1)=> (1,0)=>(0,2)=>(2,0)。我更喜欢使用图表的算法，因为例如 (0,0) 有时可能无效，但为了这个问题，我们假设它是有效的。这个问题的强力解决方案当然是创建可用对的所有排列，然后查看它们是否有效，但这显然是 O(n!) 复杂的。我很确定这可以通过某种“聪明”的方式完成。

Answer 1

在一般情况下，不同的欧拉路径的数量是顶点数量 n 的指数。仅计算无向图中欧拉回路的数量就证明是#P-complete (参见 Graham R. Brightwell 和 Peter Winkler 的 Note on Counting Eulerian Circuits)。引用维基百科:

A polynomial-time algorithm for solving a #P-complete problem, if it existed, would imply P = NP, and thus P = PH. No such algorithm is currently known.

所以也许您需要另一种方法。

但是，如果您的图形具有使指数数量的欧拉电路成为不可能的某些属性，请告诉我们这些属性。