to_prufer_sequence

to_prufer_sequence(T)

返回给定树的传递序列。

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

参数

T网络X图表

表示树的无向图对象。

返回

列表

给定树的传递序列。

加薪

NetworkXPointlessConcept

如果 T 小于2。

NotATree

如果 T 不是一棵树。

KeyError

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

参见

to_nested_tuple

from_prufer_sequence

笔记

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

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

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

工具书类

1

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