from_prufer_sequence

from_prufer_sequence(sequence)

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

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

参数:

sequencelist

一个 Prüfer 序列，它是包含 n - 2 个介于零和 n - 1（含）之间的整数的列表。

返回:

NetworkX graph

对应给定 Prüfer 序列的树。

引发:

NetworkXError

如果 Prüfer 序列无效。

另请参阅

from_nested_tuple

to_prufer_sequence

注意

从带标签的树到 Prüfer 序列存在双射。此函数是 from_prufer_sequence() 函数的逆操作。

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

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

参考文献

[1]

Wang, Xiaodong, Lei Wang, and Yingjie Wu. “Prüfer 码的最优算法。” 软件工程与应用杂志 2.02 (2009): 111. <https://doi.org/10.4236/jsea.2009.22016>

示例

Prüfer 序列和带标签的树之间存在双射，因此此函数是 to_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