from_prufer_sequence

from_prufer_sequence(sequence)

返回与给定的传递序列相对应的树。

A 传递序列 是一个列表 n -2个介于0和之间的数字 n -1，包括在内。通过将序列中的一个节点与该序列中的一个潜在程度最小的节点重复连接，可以恢复与给定的传递序列对应的树。

参数

sequence列表

Prüfer序列，这是一个列表 n 介于-2f25 0-2和-2f25-2f6之间的整数 n -1，包括首尾两项。

返回

网络X图表

与给定的传递序列相对应的树。

参见

from_nested_tuple

to_prufer_sequence

笔记

从标记的树到传递序列有一个双射。此函数与 from_prufer_sequence() 功能。

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

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

工具书类

1

王晓东、王磊和吴英杰。”普鲁弗码的最佳算法。” 软件工程与应用杂志 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