Tree#

Recognition#

识别测试#

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

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

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

总结如下：

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

NetworkX 遵循约定 “A”。明确地说，这些是：

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

对于树和树状结构，可以添加形容词 “生成” 来指定图在视为森林/分支时，由包含图中所有节点的单个树/树状结构组成。根据定义，每个树/树状结构在其定义的节点方面是生成的，因此引入 “生成” 的概念似乎是多余的。然而，节点可能代表较大图的一个子集，在这种上下文中，”生成” 成为一个有用的概念。

`is_tree`(G)	如果 `G` 是一棵树，则返回 True。
`is_forest`(G)	返回 True 如果 `G` 是一个森林。
`is_arborescence`(G)	返回 True 如果 `G` 是一个有根树。
`is_branching`(G)	如果 `G` 是一个分支，则返回 True。

Branchings and Spanning Arborescences#

寻找最优分支和生成树形结构算法。

此实现基于：

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, ...])	Returns a maximum branching from G.
`minimum_branching`(G[, attr, default, ...])	Returns a minimum branching from G.
`maximum_spanning_arborescence`(G[, attr, ...])	Returns a maximum spanning arborescence from G.
`minimum_spanning_arborescence`(G[, attr, ...])	Returns a minimum spanning arborescence from G.
`ArborescenceIterator`(G[, weight, minimum, ...])	遍历图的所有生成树，按成本递增或递减顺序。

Encoding and decoding#

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

由于树是一种高度受限的图形式，它可以以几种紧凑的方式表示。本模块包括用于以嵌套元组和Prüfer序列形式编码和解码树的函数。前者需要一个有根树，而后者可以应用于无根树。此外，Prüfer序列与标记树之间存在双射关系。

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

Operations#

树的操作。

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

返回一个新的根树，通过连接 rooted_trees 构建。

Spanning 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` 中的生成树数量。

Decomposition#

用于计算图的连接树的函数。

junction_tree(G)

返回给定图的连接树。

Exceptions#

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

NotATree

当函数期望输入一个树（即无环的连通无向图）时，却接收到一个非树图作为输入时引发此异常。