什么是生成树生成树是什么意思，VLAN中的VTP和生成树协议是什么意思，有什么作用，通俗的讲一下，不要复制，谢谢啦

VTP是用来管理交换机的，在VTP中可以将交换机置于服务器模式、客户端模式、透明模式。
服务器模式的交换机可以设置一些信息，客户端模式的交换机通过同步可以更新这些信息，比如增加VLANID。
生成树协议，是在交换机添加冗余线路时，防止产生环路的。而冗余线路的作用是防止交换机之间线路失效而增加多余的线路，生成树能让多余的线路处于阻塞状态，一旦某转发状态的接口DOWN掉，冗余线路可以自动进入转发状态。

图的生成树

在一个图中，每条边或弧可以拥有一个与之相关的数值，我们将它称为权。这些权可以具有一定的含义，比如，表示一个顶点到达另一个顶点的距离、所花费的时间、线路的造价等等。这种带权的图通常被称作网。
图或网的生成树不是唯一的，从不同的顶点出发可以生成不同的生成树，但n个结点的生成树一定有n-1条边
下面我们计算一下上面两棵生成树的权值之和。第一棵生成树的权值总和是：16+11+5+6+18=56；第二棵生成树的权值是：16+19+33+18+6=92。通常我们将权值总和最小的生成树称为最小生成树。
构造最小生成树的方法：最初生成树为空，即没有一个结点和一条边，首先选择一个顶点作为生成树的根，然后每次从不在生成树中的边中选择一条权值尽可能小的边，为了保证加入到生成树中的边不会造成回路，与该边邻接的两个顶点必须一个已经在生成树中，一个则不在生成树中，若网中有n个顶点，这里考虑的网是一个连通无向图，则按这种条件选择n-1边就可以得到这个网的最小生成树了。详细的过程可以描述为：设置2个集合，U集合中的元素是在生成树中的结点，V-U集合中的元素是不在生成树中的顶点。首先选择一个作为生成树根结点的顶点，并将它放入U集合，然后在那些一端顶点在U集合中，而另一端顶点在V-U集合中的边中找一条权最小的边，并把这条边和那个不在U集合中的顶点加入到生成树中，即输出这条边，然后将其顶点添加到U集合中，重复这个操作n-1次。
下面我们考虑一下如何实现这个操作过程的算法。
分析：，1它主要有两项操作：按条件选择一条边和将顶点加入到U集合中；，2网中的每个顶点不是在U集合中，就是在V-U集合中。为了提高算法的时间、空间效率，我们将为这个算法设计一个辅助数组closedge，用来记录从集合U到集合V-U具有最小权值的边。对每个属于V-U集合的顶点，在辅助数组中存在一个相应的分量closedge[i-1]，它包括两个域，一个域用来表示在该顶点与V-U集合中某些顶点构成的边中权最小的那条边的权值，若该顶点进入U集合，则值为0；另一个域表示这条最小权值的边对应的在V-U集合中的顶点下标。其类型定义如下所示：#defineMAX_NUM10struct{intadjvex;floatlowcist;}closedge[MAX_NUM];整个算法的执行过程可以描述为：{初始化closedge数组的内容；选择某个顶点k作为生成树的根结点，并将它加入到U集合中；重复下列操作n-1次：l选择一条满足条件的边；l输出这条边的两个端点；l修改V-U集合中的顶点信息，即与U集合中构成最小权值的边。}假设该网以邻接矩阵的形式给出，则完整的算法为：voidMini_SpanTree(GraphG,intk,intn){//G是网的邻接矩阵，k是生成树根结点的序号，n是网的顶点数目for(j=0;j<n;j++)if(j!=k)closedge[j]={k,G[k][j]};closedge[k].lowcost=0;for(i=1;i<n;i++){k=minmun(closedge);printf(k,closedge[k].adjvex);closedge[k].lowcost=0;//将顶点加入U集合中for(j=0;j<n;j++)if(closedge&&G[k][j]<closedge[j].lowcost)closedge[j]={k,G[k][j]};}}

生成树的标准有哪些？各有什么异同

一区别

最小生成树能够保证整个拓扑图的所有路径之和最小，但不能保证任意两点之间是最短路径。

最短路径是从一点出发，到达目的地的路径最小。

二实现方法

1. 最小生成树

2. 最小生成树有两种算法来得到：Prims算法和Kruskal算法。

3. Kruskal算法：根据边的加权值以递增的方式，一次找出加权值最低的边来构建最小生成树，而且规定：每次添加的边不能造成生成树有回路，知道找到N-1个边为止。

4. Prims算法：以每次加入一个的临界边来建立最小生成树，直到找到N-1个边为止。其规则为：以开始时生成树的集合，集合U为起始的定点，然后找出与生成树集合邻接的边，集合V中，加权值最小的边来建立生成树，为了确定新加入的边不会造成回路，所以每一个新加入的边，只允许有一个顶点在生成树集合中，重复执行此步骤，直到找到N-1个边为止。

5. 2最短路径

算法描述

(这里描述的是从节点1开始到各点的dijkstra算法，其中Wa->b表示a->b的边的权值，d(i)即为最短路径值)

1．置集合S={2,3,n},数组d(1)=0,d(i)=W1->i(1,i之间存在边)or+无穷大(1.i之间不存在边)

2．在S中，令d(j)=min{d(i),i属于S}，令S=S-{j}，若S为空集则算法结束，否则转3

3．对全部i属于S,如果存在边j->i，那么置d(i)=min{d(i),d(j)+Wj->i}，转2

Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合，用S表示，初始时S中只有一个源点，以后每求得一条最短路径,就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了，第二组为其余未确定最短路径的顶点集合，用U表示，按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

算法具体步骤

，1初始时，S只包含源点，即S=，v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权，若v与u有边或∞(若u不是v的出边邻接点。

，2从U中选取一个距离v最小的顶点k，把k，加入S中，该选定的距离就是v到k的最短路径长度。

，3以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u，uU的距离，经过顶点k比原来距离，不经过顶点k短，则修改顶点u的距离值，修改后的距离值为顶点k的距离加上边上的权。

，4重复步骤，2和，3直到所有顶点都包含在S中。

复杂度分析

Dijkstra算法的时间复杂度为O(n^2)空间复杂度取决于存储方式，邻接矩阵为O(n^2)

组播生成树的概念是什么，能给解释下吗？

组播生成树也叫分发树,即组播源把数据固定传到一个路由器上,再由该路由器把数据发给其它路由,过程中所形成的路径吧