查找图上所有边的路径
Finding the Path of all Edges on a Graph
我正在尝试在覆盖所有边的图形上获取路径，并且只遍历它们一次。
这意味着只有两个 "end" 点——它们将有奇数个附加节点。这些端点要么有一个连接边，要么是环路的一部分并有 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
我试图找到解决此问题的算法名称，并认为是 "Chinese Postman Problem"，但基于 https://github.com/rkistner/chinese-postman/blob/master/postman.py 处的代码实现此算法并没有提供我的结果预期的。
欧拉路径看起来几乎是所需要的，但 networkx implementation 仅适用于封闭（环状）网络。
我也查看了 Hamiltonian Path - and tried the networkx algorithm - 但不支持图表类型。
理想情况下，我想使用 Python 和 networkx 来实现它，可能有一个简单的解决方案已经包含在库中，但我似乎找不到。
您要查找的 Eulerian Path that visits every edge exactly once. You can use Fleury's algorithm to generate the path. Fleury's algorithm has O(E^2) time complexity, if you need more efficient algorithm check Hierholzer's algorithm 是 O(E)。
还有一个unmerged pull request for the networkx library that implements this. The source好用
（对于 networkx 1.11，.edge 必须替换为 .edge_iter）。
这被称为 Eulerian Path of a graph. It has now been added to NetworkX as eulerian_path()。
我正在尝试在覆盖所有边的图形上获取路径，并且只遍历它们一次。 这意味着只有两个 "end" 点——它们将有奇数个附加节点。这些端点要么有一个连接边，要么是环路的一部分并有 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
我试图找到解决此问题的算法名称，并认为是 "Chinese Postman Problem"，但基于 https://github.com/rkistner/chinese-postman/blob/master/postman.py 处的代码实现此算法并没有提供我的结果预期的。
欧拉路径看起来几乎是所需要的，但 networkx implementation 仅适用于封闭（环状）网络。
我也查看了 Hamiltonian Path - and tried the networkx algorithm - 但不支持图表类型。
理想情况下，我想使用 Python 和 networkx 来实现它，可能有一个简单的解决方案已经包含在库中，但我似乎找不到。
您要查找的 Eulerian Path that visits every edge exactly once. You can use Fleury's algorithm to generate the path. Fleury's algorithm has O(E^2) time complexity, if you need more efficient algorithm check Hierholzer's algorithm 是 O(E)。
还有一个unmerged pull request for the networkx library that implements this. The source好用
（对于 networkx 1.11，.edge 必须替换为 .edge_iter）。
这被称为 Eulerian Path of a graph. It has now been added to NetworkX as eulerian_path()。