to_prufer_sequence#

to_prufer_sequence(T)[source]#

返回给定树的 Prüfer 序列。

一个 Prüfer 序列 是一个包含 *n* - 2 个介于 0 和 *n* - 1（包括）之间的数字的列表。可以通过重复地将序列中的一个节点与根据序列具有最小潜在度的节点连接起来，来恢复与给定 Prüfer 序列对应的树。

参数:
TNetworkX 图对象

表示树的无向图对象。

返回值:
list

给定树的 Prüfer 序列。

引发:
NetworkXPointlessConcept

如果 T 中的节点数小于两个。

NotATree

如果 T 不是树。

KeyError

如果 T 中的节点集不是 {0, …, n - 1}。

另请参阅

to_nested_tuple
from_prufer_sequence

注意

标定树（labeled tree）与 Prüfer 序列之间存在双射。此函数是 from_prufer_sequence() 函数的逆运算。

有时 Prüfer 序列使用从 1 到 *n* 编号的节点，而不是从 0 到 *n* - 1 编号。此函数要求节点采用后一种编号形式。您可以使用 relabel_nodes() 函数将树中的节点重新编号为适当的格式。

此实现来自 [1]，其运行时间为 \(O(n)\)。

参考文献

[1]

Wang, Xiaodong, Lei Wang, and Yingjie Wu. “An optimal algorithm for Prufer codes.” Journal of Software Engineering and Applications 2.02 (2009): 111. <https://doi.org/10.4236/jsea.2009.22016>

示例

Prüfer 序列与标定树之间存在双射，因此此函数是 from_prufer_sequence() 函数的逆运算

>>> edges = [(0, 3), (1, 3), (2, 3), (3, 4), (4, 5)]
>>> tree = nx.Graph(edges)
>>> sequence = nx.to_prufer_sequence(tree)
>>> sequence
[3, 3, 3, 4]
>>> tree2 = nx.from_prufer_sequence(sequence)
>>> list(tree2.edges()) == edges
True
在本页