生成树算法是

⑴ 图的相关算法（二）：最小生成树算法

在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。

例如，对于上图中的连通网可以有多棵权值总和不相同的生成树。

克鲁斯卡尔（Kruskal）算法，是用来求加权连通图的最小生成树的算法。

基本思想 ：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。
具体做法 ：首先构造一个只含n个顶点的森林，然后依照权值从小到大从连通网中选择边加入到森林羡册乎中，并使得森林不产生回路，直到森林变成一棵树为止。

以图G4为例（更详细的可以参考《算法导论》p367），对Kruskal进行演示（假设，用数组R保存最小生成树结果）。

第1步 ：将边<E,F>加入R中。
边<兄悉E,F>的权值最小，因此将它加入到最小生成树结果R中。
第2步 ：将边<C,D>加入R中。
上一步操作之后，边<C,D>的权值最小，因此将它加入到最小生成树结果R中。
第3步 ：将边<D,E>加入R中。
上一步操作之后，边<D,E>的权值最小，因此将它加入到最小生成树结果R中。
第4步 ：将边<B,F>加入R中。
上一步操作之后，边<C,E>的权值最小，但<C,E>会和已有的边构成回路；因此，跳过边<C,E>。同理，跳过边<C,F>。将边<B,F>加入到最小生成树结果R中。
第5步 ：将边<E,G>加入R中。
上一步操作之后，边<E,G>的权值最小，因此将它加入到最小生成树结果R中。
第6步 ：将边<A,B>加入R中。
上一步操作之后，边<F,G>的权值最小，但<F,G>会和已有的边构成回路；因此，跳过边<F,G>。同理，跳过边<B,C>。将边<A,B>加入到最小生成树结果R中。

此时，最小生成树构造完成！它包括的边依次是： <E,F> <C,D> <D,E> <B,F> <E,G> <A,B> 。

根据前面介绍的克鲁斯卡尔算法的基本思想和做法，我们能够了解到，克鲁斯卡尔算法重点需要解决的以下两个问题：
问题一 对图的所有边按照权值大小进行排序。
问题二 将边添加到最小生成树中时，怎么样判断是否形成了回路。

问题一用排序算法排序即可。
问题二，处理方式：记录顶点在“最小生成树”中的终点，顶点的终点是“在最小生成树中与它连通的最大顶点"(关于这一点，后面会通过图片给出说明)。然后每次需要将一条边添加到最小生成树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。 以下图来进行说明：

在将<E,F> <C,D> <D,E>加入到最小生成树R中之后，这几条边的顶点就都有了终点：

关于终点，姿迹就是将所有顶点按照从小到大的顺序排列好之后；某个顶点的终点就是"与它连通的最大顶点"。 因此，接下来，虽然<C,E>是权值最小的边。但是C和E的重点都是F，即它们的终点相同，因此，将<C,E>加入最小生成树的话，会形成回路。这就是判断回路的方式。

普里姆（Prim）算法，也是求加权连通图的最小生成树的算法。

基本思想
对于图G而言，V是所有顶点的集合；现在，设置两个新的集合U和T，其中U用于存放G的最小生成树中的顶点，T存放G的最小生成树中的边。从所有的 uЄU ，vЄ(V-U)（V-U表示除去U的所有顶点）的边中选取权值最小的边（u，v），将顶点v加入U中，将边（u,v）加入集合T中，如此不断重复，直到U=V为止，最小生成树构造完毕，此时集合T中包含了最小生成树中的所有边。

以上图G4为例，来对普里姆进行演示(从第一个顶点A开始通过普里姆算法生成最小生成树)。

初始状态 ：V是所有顶点的集合，即V={A,B,C,D,E,F,G}；U和T都是空！
第1步 ：将顶点A加入到U中。
此时，U={A}。
第2步 ：将顶点B加入到U中。
上一步操作之后，U={A}, V-U={B,C,D,E,F,G}；因此，边(A,B)的权值最小。将顶点B添加到U中；此时，U={A,B}。
第3步 ：将顶点F加入到U中。
上一步操作之后，U={A,B}, V-U={C,D,E,F,G}；因此，边(B,F)的权值最小。将顶点F添加到U中；此时，U={A,B,F}。
第4步 ：将顶点E加入到U中。
上一步操作之后，U={A,B,F}, V-U={C,D,E,G}；因此，边(F,E)的权值最小。将顶点E添加到U中；此时，U={A,B,F,E}。
第5步 ：将顶点D加入到U中。
上一步操作之后，U={A,B,F,E}, V-U={C,D,G}；因此，边(E,D)的权值最小。将顶点D添加到U中；此时，U={A,B,F,E,D}。
第6步 ：将顶点C加入到U中。
上一步操作之后，U={A,B,F,E,D}, V-U={C,G}；因此，边(D,C)的权值最小。将顶点C添加到U中；此时，U={A,B,F,E,D,C}。
第7步 ：将顶点G加入到U中。
上一步操作之后，U={A,B,F,E,D,C}, V-U={G}；因此，边(F,G)的权值最小。将顶点G添加到U中；此时，U=V。

此时，最小生成树构造完成！它包括的顶点依次是：A B F E D C G。

⑵ 生成树算法

“生成树”资料

交换机内的生成树算法（STA）使你可以创建一条备用链路（当网络中存在多台交换机时）。在主链路正常工作时，备用链路处于空闲状态（不工作）；只有在主链路出现问题时，备用链路才不需要任何人工干预自动地接替主链路。

这种自动重构的功能，使得网络上的用户能够最大限度地与网络保持正常的连接。生成树算法较复杂，所以，建议最好在充分研究理解其之后，再更改其一些设置。请仔细阅读并理解下述内容之后，再去更改交换机上的生成树的默认设置。

网络环路的侦测和预防（Network loop detection and prevention）：任何两个局域网之间应该只有一条路径，否则，网络中将出现环路。如果存在着多于一条的路径，那么生成树算法将会侦测到环路的发生，并自动选择开销值（c ost）最低的那条路径作为可使用的路径（主链路），而阻断其它路径，将它们作为备用路径（备用链路）。

自动拓扑重构（Automatic topology re-configuration）：当主链路出现故障时，生成树算法将自动启用备用链路，重构网络结构。

生成树的级别（STA Operation Levels）

生成树有两种工作级别：桥级别（bridge level）和端口级别（port level）。在桥一级上，生成树算法为每台交换机计算桥的标志级数（Bridge Identifier），然后设定根桥（Root Bridge）和指定桥（Designated Bridges）。而在端口一级上，生成树算法设定根端口（Root Port）和指定端口（Designated Ports）。详述如下：

在桥一级上（On the Bridge Level）：

根桥（Root Bridge）：具有最小桥标志级数的（lowest Bridge Identifier）交换机是根桥（Root Bridge）。当然，你希望根桥是环路中所有交换机当中最好的一台（交换机），以保证能够提供最好的网络性能和可靠性。

桥标志级数（Bridge Identifier）：桥标志级数是桥的优先级（Bridge Priority）和交换机的MAC地址的综合数值，其中桥的优先级（Bridge Priority）是一个你可以设定的参数。例如，“4 00 80 C8 00 01 00”中的“4”是桥的优先级，“00 80 C8 00 01 00”是交换机的MAC地址。交换机的桥标志级数越低，则交换机的优先级越高，这样可以增加其成为根桥的可能性。

指定桥（Designated Bridge）：在每个网段中，到根桥（Root Bridge）的路径开销最低的（lowest Root Path Cost）桥将成为指定桥（Designated Bridge），数据包将通过它转发到网段。一旦所有的交换机具有相同的根路径开销（Root Path Cost），那么具有最低的桥标志级数的（lowest Bridge Identifier）交换机才会被定为指定桥（De signated Bridge）。

根路径开销（Root Path Cost）：一台交换机的根路径开销（Root Path Cost）是根端口（Root Port）的路径开销（Path Cost）与数据包经过的所有交换机的根路径开销（Root Path Cost）之和。根桥（Root Bridge）的根路径开销（Root Path Cost）是零。

桥的优先级（Bridge Priority）：是一个用户可以设定的参数。设定的值越小，优先级越高。交换机具有越高的优先级，才越有可能成为根桥。

在端口一级上（On the Port Level）：

根端口（Root Port）：每台交换机都有一个根端口（Root Port），这个端口到根桥的路径开销最低。一旦多个端口具有相同的到根桥的路径开销时，那么具有最低的端口标志级别的才会成为根端口。

指定端口（Designated Port）：指定端口就是指定桥（Designated Bridge）上的端口。

端口优先级（Port Priority）：数值越小，端口的优先级就越高。具有越高端口优先级，才越有可能成为根端口。

路径开销（Path Cost）：这是一个可变的参数，它将随着生成树中的设定值的变化而变化。依据STA的默认参数值，每个1000Mbps网段有一个指定的路径开销值为4 ，100Mbps网段的路径开销值19，10Mbps网段的路径开销值100.

生成树参数（STA Parameters）

生成树的参数用户可以根据自己的需要进行修改，但是建议最好使用出厂时的默认设置。除非确实需要对出厂设置值进行变动时，再去改动默认值。用户可以改动的生成树参数有如下几个：

桥优先级（Bridge Priority）：数值范围从0到65535.“0”的优先级最高。

呼叫时间（Bridge Hello Time）：数值范围从1秒到10秒。是指根桥向其它所有交换机发出BPDU数据包的时间间隔，以告知其它所有交换机它是根桥。如果你的交换机还未是根桥时为其设置了呼叫时间，那么，一旦你的交换机成为根桥，该呼叫时间就会派上用处。

注意：呼叫时间不能大于桥的最大老化时间（Max. Age），否则，将出现错误信息。

最大的桥老化时间（Bridge Max. Age）：数值范围从6秒到40秒。如果在超出最大老化时间之后，还没有收到根桥发出的BPDU数据包，那么，在允许的条件下你的交换机将充当根桥向其它所有的交换机发出B PDU数据包。如果交换机确实具有最小的桥标志级数，那么，它将随之成为根桥。

桥转发时延（Bridge Forward Delay）：数值范围从4秒到30秒。是指交换机的端口从阻塞状态转为转发状态所用的监听时间。

当你欲变动生成树参数时，请一定记住下述公式：

最大的桥老化时间≤ 2 x（桥转发时延 – 1秒）

即：Max. Age ≤ 2 x （Forward Delay - 1 second）

最大的桥老化时间≥ 2 x（呼叫时间 + 1秒）

即：Max. Age ≥ 2 x （Hello Time + 1 second）

端口优先级（Port Priority）：数值范围从0到255.数值越小，那么该端口越可能成为根端口。

⑶ 最小生成树的两种算法

主要有两个：
1.普里姆（Prim)算法
特点：时间复杂度为O(n2).适合于求边稠密的最小生成树。
2.克鲁斯卡尔（Kruskal)算法
特点：时间复杂度为O(eloge)(e为网中边数），适合于求稀疏的网的最小生成树。