欧拉回路#

eulerian_circuit(G, source=None, keys=False)[source]#

返回 G 中欧拉回路的边的迭代器。

欧拉回路是包含图中每条边恰好一次的闭合游走。

参数:

GNetworkX 图: 一个图，可以是有向的或无向的。
source节点，可选: 回路的起始节点。
keys布尔值: 如果为 False，此函数生成的边将采用 (u, v) 的形式。否则，边将采用 (u, v, k) 的形式。除非 G 是多重图，否则此选项将被忽略。

返回值:

edges迭代器: 欧拉回路中边的迭代器。

引发异常:

NetworkXError: 如果图不是欧拉图。

另请参阅

is_eulerian

注意

这是根据 [1] 中的算法改编的线性时间实现。

有关欧拉环游的一般信息，请参阅 [2]。

参考文献

[1]

J. Edmonds, E. L. Johnson. Matching, Euler tours and the Chinese postman. Mathematical programming, Volume 5, Issue 1 (1973), 111-114.

[2]

https://en.wikipedia.org/wiki/Eulerian_path

示例

获取无向图中的欧拉回路

>>> G = nx.complete_graph(3)
>>> list(nx.eulerian_circuit(G))
[(0, 2), (2, 1), (1, 0)]
>>> list(nx.eulerian_circuit(G, source=1))
[(1, 2), (2, 0), (0, 1)]

获取欧拉回路中的顶点序列

>>> [u for u, v in nx.eulerian_circuit(G)]
[0, 2, 1]