树#

识别#

识别测试#

森林是一个无环无向图，而树是一个连通的森林。根据子领域的不同，将这些定义推广到有向图有多种约定俗成的方式。

在一种约定中，有向森林和树的变体以相同的方式定义，只是忽略边的方向。实际上，每条有向边都被视为一条无向边。然后，施加额外的限制来定义分支和树形图。

在另一种约定中，有向森林和树的变体分别对应于前一种约定的分支和树形图。然后定义了两个新术语：多森林和多树，以对应于另一种约定的森林和树。

总结

+-----------------------------+
| Convention A | Convention B |
+=============================+
| forest       | polyforest   |
| tree         | polytree     |
| branching    | forest       |
| arborescence | tree         |
+-----------------------------+

每种约定都有其理由。第一种约定强调定义上的相似性，即有向森林和树只关注无环性，没有入度限制，就像它们的无向对应物一样。第二种约定强调功能上的相似性，其意义在于生成树的有向模拟是生成树形图。也就是说，取任意生成树并选择一个节点作为根。然后为每条边指定方向，使得从根到其他每个节点都存在有向路径。结果就是生成树形图。

NetworkX 遵循约定“A”。具体来说，它们是

无向森林: 没有无向环的无向图。
无向树: 连通的无向森林。
有向森林: 没有无向环的有向图。等价地，底层图结构（忽略边的方向）是无向森林。在约定 B 中，这称为多森林（polyforest）。
有向树: 弱连通的有向森林。等价地，底层图结构（忽略边的方向）是无向树。在约定 B 中，这称为多树（polytree）。
分支: 每个节点至多有一个父节点的有向森林。因此最大入度等于 1。在约定 B 中，这称为森林（forest）。
树形图: 每个节点至多有一个父节点的有向树。因此最大入度等于 1。在约定 B 中，这称为树（tree）。

对于树和树形图，可以添加形容词“生成”（spanning）来表示该图（当被视为森林/分支时）由一个包含图中所有节点的单个树/树形图组成。根据定义，每个树/树形图在其定义的节点上都是生成的，因此引入“生成”的概念似乎是多余的。然而，这些节点可能代表较大图中的一个节点子集，正是在这种背景下，“生成”一词成为一个有用的概念。

`is_tree`(G)	如果 `G` 是树，则返回 True。
`is_forest`(G)	如果 `G` 是森林，则返回 True。
`is_arborescence`(G)	如果 `G` 是树形图，则返回 True。
`is_branching`(G)	如果 `G` 是分支，则返回 True。

分支和生成树形图#

用于寻找最优分支和生成树形图的算法。

此实现基于

J. Edmonds, 最优分支, J. Res. Natl. Bur. Standards 71B (1967), 233–240. URL: http://archive.org/details/jresv71Bn4p233

`branching_weight`(G[, attr, default])	返回分支的总权重。
`greedy_branching`(G[, attr, default, kind, seed])	通过贪心算法获得的分支。
`maximum_branching`(G[, attr, default, ...])	返回 G 中的最大分支。
`minimum_branching`(G[, attr, default, ...])	返回 G 中的最小分支。
`maximum_spanning_arborescence`(G[, attr, ...])	返回 G 中的最大生成树形图。
`minimum_spanning_arborescence`(G[, attr, ...])	返回 G 中的最小生成树形图。
`ArborescenceIterator`(G[, weight, minimum, ...])	以递增或递减的成本迭代图中的所有生成树形图。

编码与解码#

用于编码和解码树的函数。

由于树是图的一种高度受限形式，因此可以用多种方式简洁地表示它。此模块包含用于以嵌套元组和 Prüfer 序列形式对树进行编码和解码的函数。前者需要有根树，而后者可应用于无根树。此外，从 Prüfer 序列到带标签树之间存在双射。

`from_nested_tuple`(sequence[, ...])	返回与给定嵌套元组对应的有根树。
`to_nested_tuple`(T, root[, canonical_form])	返回给定树的嵌套元组表示。
`from_prufer_sequence`(sequence)	返回与给定 Prüfer 序列对应的树。
`to_prufer_sequence`(T)	返回给定树的 Prüfer 序列。

操作#

对树进行的操作。

join_trees(rooted_trees, *[, ...])

通过连接 rooted_trees 返回一个新的有根树

生成树#

计算最小/最大生成树/森林的算法。

`minimum_spanning_tree`(G[, weight, ...])	返回无向图 `G` 上的最小生成树或森林。
`maximum_spanning_tree`(G[, weight, ...])	返回无向图 `G` 上的最大生成树或森林。
`random_spanning_tree`(G[, weight, ...])	使用 `G` 的边权重采样一个随机生成树。
`minimum_spanning_edges`(G[, algorithm, ...])	生成无向加权图的最小生成森林中的边。
`maximum_spanning_edges`(G[, algorithm, ...])	生成无向加权图的最大生成森林中的边。
`SpanningTreeIterator`(G[, weight, minimum, ...])	以递增或递减的成本迭代图中的所有生成树。
`number_of_spanning_trees`(G, *[, root, weight])	返回 `G` 中的生成树数量。

分解#

计算图的连接树的函数。

junction_tree(G)

返回给定图的连接树。

异常#

用于编码和解码树的函数。

NotATree

当函数期望输入为树（即没有环的连通无向图）但实际输入是非树图时引发此异常。