python - 查找图上所有边的路径

Question

我试图在覆盖所有边的图形上获取路径，并且只遍历它们一次。 这意味着只有两个“端”点——它们将有奇数个附加节点。这些端点要么有一个连接边，要么是环路的一部分并有 3 个连接。

所以在下面的简单情况下，我需要按 1-2-3-4-5(或 5-4-3-2-1)的顺序遍历节点:

在更复杂的情况下，路径将是 1-2-3-4-2(或 1-2-4-3-2):

下面也是一个有效的图，有 2 个端点:1-2-4-3-2-5

我试图找到解决此问题的算法名称，并认为这是“中国 postman 问题”，但基于 https://github.com/rkistner/chinese-postman/blob/master/postman.py 处的代码实现了此问题没有提供我预期的结果。

欧拉路径看起来几乎是所需要的，但是 networkx implementation仅适用于封闭(环路)网络。

我还看了一个 Hamiltonian Path - 并尝试了 networkx algorithm - 但不支持图形类型。

理想情况下，我想使用 Python 和 networkx 来实现它，可能有一个简单的解决方案已经是库的一部分，但我似乎找不到它。

Answer 1

您正在寻找 Eulerian Path恰好访问每条边一次。您可以使用 Fleury's algorithm生成路径。 Fleury的算法有O(E^2)的时间复杂度，如果需要更高效的算法检查Hierholzer's algorithm而是 O(E)。

还有一个 unmerged pull request对于实现这个的 networkx 库。 source易于使用。

(对于 networkx 1.11，.edge 必须替换为 .edge_iter)。