在一个图中查找所有边的路径

Question

我正在尝试获取覆盖所有边缘并仅遍历一次的图形路径。 这意味着只会有两个“端点” - 它们将具有奇数数量的连接节点。这些端点要么具有一个连接边，要么是循环的一部分并具有3个连接点。

因此，在下面的简单情况中，我需要按照以下顺序遍历节点1-2-3-4-5（或5-4-3-2-1）：

在下面更加复杂的情况下，路径将是1-2-3-4-2（或1-2-4-3-2）：

以下也是一个有效的图形，有两个端点：1-2-4-3-2-5

我曾试图寻找一个解决这个问题的算法，并认为它是“中国邮递员问题”，但基于 https://github.com/rkistner/chinese-postman/blob/master/postman.py 的代码实现并没有提供我期望的结果。

欧拉路径看起来几乎符合要求，但是 networkx 实现 仅适用于封闭（环形）网络。

我还看了一下 哈密顿路径 - 并尝试了 networkx 算法 - 但不支持该图类型。

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

- geographika

---

汉密尔顿路径覆盖所有顶点，你可能需要查看覆盖边而不是顶点的欧拉路径。GeeksForGeeks 网站上似乎有 Python 的示例实现。 - niemmi

@niemmi - 谢谢！看起来我要找的术语是欧拉路径（而不是电路）。我会查看算法，看看是否可以使用现有的networkx方法简化它。 - geographika

@niemmi，你是对的，你可以通过添加适当的链接将其转化为答案。 - Abhishek J

这被称为图的Eulerian Path。现在已经作为eulerian_path()添加到了networkx中。 - iacob

Answer 1

您正在寻找访问每条边恰好一次的欧拉路径。 您可以使用Fleury算法生成该路径。 Fleury算法的时间复杂度为 O(E^2)，如果您需要更高效的算法，请查看Hierholzer算法，其时间复杂度为 O(E)。

此外，networkx库还有一个未合并的拉取请求实现了这个功能。 源代码易于使用。

（对于networkx 1.11，必须将.edge替换为.edge_iter）。

- niemmi

---

一旦我确定了我要查找的路径类型的名称，我就可以在networkx中找到一个实现。 - geographika

请注意：由于路径查找算法实现中存在根本问题，因此该拉取请求已关闭。 - iacob

@niemmi 为什么Hierholzer算法的时间复杂度不是O(V+E)？ - African_king

@African_king 因为算法不必关心度数为0的顶点。换句话说，为了走N条边的路径，你必须访问N+1个顶点。算法的起点可以通过选择一条随机边并选择其中一个顶点来找到，而不是迭代顶点以找到度数> 0的顶点。 - niemmi

Answer 2

这被称为图的欧拉路径。现在已经被添加到 NetworkX 中，作为 eulerian_path() 函数。

- iacob