hamiltonian_path

hamiltonian_path(G)

返回给定竞赛图中的哈密顿路径。

每个竞赛图都存在哈密顿路径。如果竞赛图还是强连通的，那么返回的哈密顿路径可以通过连接路径的端点形成哈密顿回路。

Parameters:

GNetworkX 图

表示竞赛的有向图。

Returns:

path列表

在 G 中形成哈密顿路径的节点列表。

Notes

这是一个递归实现，其渐近运行时间为 \(O(n^2)\)，忽略乘法的多对数因子，其中 \(n\) 是图中节点的数量。

Examples

>>> G = nx.DiGraph([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)])
>>> nx.is_tournament(G)
True
>>> nx.tournament.hamiltonian_path(G)
[0, 1, 2, 3]