from_prufer_sequence

from_prufer_sequence(sequence)

返回与给定普吕弗序列对应的树。

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

Parameters:

sequencelist

一个普吕弗序列，即包含 n - 2 个介于零和 n - 1 之间的整数的列表。

Returns:

NetworkX 图

与给定普吕弗序列对应的树。

Raises:

NetworkXError

如果普吕弗序列无效。

See also

from_nested_tuple

to_prufer_sequence

Notes

从标记树到普吕弗序列存在一一对应关系。此函数是 from_prufer_sequence() 函数的逆函数。

有时普吕弗序列使用从 1 到 n 标记的节点，而不是从 0 到 n - 1。此函数要求节点以 0 到 n - 1 的形式标记。您可以使用 networkx.relabel_nodes() 重新标记树的节点以符合此格式。

此实现来自 [1]，具有 \(O(n)\) 的运行时间。

References

[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>

Examples

普吕弗序列与标记树之间存在一一对应关系，因此此函数是 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