树#

识别#

识别测试#

A 森林是无圈无向图，并且 tree 是一个连接的林。根据子字段的不同，将这些定义归纳为有向图有多种约定。

在一个惯例中，森林和树的定向变体以相同的方式定义，只是边缘的方向被忽略。实际上，每个有向边都被视为单个无向边。然后，附加限制来定义枝条和 树枝状 .

在另一公约中，森林和树木的定向变种分别对应于前一公约的分支和乔木。然后是两个新学期， 混交林 和 超树推理法 ，定义为与另一公约的森林和树木相对应。

总结：

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

每项公约都有其理由。第一个公约强调定义上的相似性，即定向森林和树木只与非循环性有关，没有程度上的限制，正如它们的无向对应物没有程度上的限制一样。第二个约定强调功能相似性，即生成树的有向模拟是生成树形图。也就是说，取任意生成树并选择一个节点作为根。然后，每个边都被指定一个方向，这样就有一个从根到其他每个节点的定向路径。结果是形成了一个跨越的树形图。

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

无向森林: 没有无向圈的无向图。
无向树: 一个相连的、无向的森林。
定向森林: 没有无向圈的有向图。同样地，底层图形结构（忽略边缘方向）是无向林。在公约B中，这被称为多森林。
有向树: 弱连接的定向森林。同样地，基础图结构（忽略边方向）是无向树。在公约B中，这被称为多棵树。
分支: 每个节点最多有一个父节点的定向林。所以最大度数等于1。在公约B中，这被称为森林。
树状植物: 有向树，每个节点最多有一个父节点。所以最大度数等于1。在公约B中，这被称为树。

对于树木和树木，可以添加形容词“跨越”来表示当图被视为一个森林/分支时，它由一个包含图中所有节点的树/树木组成。根据定义，每一棵树/树木都是相对于定义树/树的节点进行跨越的，因此，引入“跨越”概念似乎是多余的。然而，节点可以表示一个更大的图中节点的一个子集，在这个上下文中，“跨越”一词成为一个有用的概念。

`is_tree`(G)	返回true `G` 是一棵树。
`is_forest`(G)	返回true `G` 是一片森林。
`is_arborescence`(G)	返回true `G` 是一种乔木。
`is_branching`(G)	返回true `G` 是分支。

树枝和跨越乔木#

寻找最佳分支和跨越乔木的算法。

此实施基于：

J.Edmonds，最佳分支，J.Res.Natl.Bur。标准71B（1967），233–240。网址：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, ...])	以递增或递减的代价迭代图的所有生成树状图。
`Edmonds`(G[, seed])	埃德蒙兹算法 [R5a58a7577195-1] 用于寻找最佳的分枝和横跨树冠。

编码和解码#

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

由于树是一种高度受限的图形形式，因此它可以用多种方式简洁地表示。该模块包括以嵌套元组和传递序列的形式对树进行编码和解码的功能。前者需要有根的树，而后者可以应用于无根的树。此外，有一个双射从pr护fer序列到标记树。

`from_nested_tuple`(sequence[, ...])	返回与给定嵌套元组对应的根目录树。
`to_nested_tuple`(T, root[, canonical_form])	返回给定树的嵌套元组表示形式。
`from_prufer_sequence`(sequence)	返回与给定的传递序列相对应的树。
`to_prufer_sequence`(T)	返回给定树的传递序列。

操作#

对树木的操作。

join(rooted_trees[, label_attribute])

返回一个新的根目录树，其中根节点与每个给定根目录树的根相连接。

生成树#

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

`minimum_spanning_tree`(G[, weight, ...])	返回无向图上的最小生成树或林 `G` .
`maximum_spanning_tree`(G[, weight, ...])	返回无向图上的最大生成树或林 `G` .
`minimum_spanning_edges`(G[, algorithm, ...])	在无向加权图的最小生成林中生成边。
`maximum_spanning_edges`(G[, algorithm, ...])	在无向加权图的最大生成林中生成边。
`SpanningTreeIterator`(G[, weight, minimum, ...])	以递增或递减的代价遍历图的所有生成树。

分解#

计算图的连接树的函数。

junction_tree(G)

返回给定图的连接树。

例外情况#

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

NotATree

当函数需要一个树（即一个没有循环的连接无向图）但得到一个非树图作为输入时引发。