关键词：
STP（Spanning Tree Protocol）是生成树协议的英文缩写。该协议可应用于在网络中建立树形拓扑，消除网络中的二层环路，并且可以通过一定的方法实现路径冗余，但不是一定可以实现路径冗余。生成树协议适合所有厂商的网络设备，在配置上和体现功能强度上有所差别，但是在原理和应用效果是一致的
STP的基本原理是，通过在交换机之间传递一种特殊的协议报文，网桥协议数据单元（Bridge Protocol Data Unit，简称BPDU），来确定网络的拓扑结构。BPDU有两种，配置BPDU（Configuration BPDU）和TCN BPDU。前者是用于计算无环的生成树的，后者则是用于在二层网络拓扑发生变化时产生用来缩短MAC表项的刷新时间的（由默认的300s缩短为15s）。
Spanning Tree Protocol(STP)在IEEE802.1D文档中定义。该协议的原理是按照树的结构来构造网络拓扑，消除网络中的环路，避免由于环路的存在而造成广播风暴问题。
Spanning Tree Protocol(STP)的基本思想就是按照"树"的结构构造网络的拓扑结构，树的根是一个称为根桥的桥设备，根桥的确立是由交换机或网桥的BID（Bridge ID）确定的，BID最小的设备成为二层网络中的根桥。BID又是由网桥优先级和MAC地址构成，不同厂商的设备的网桥优先级的字节个数可能不同。由根桥开始，逐级形成一棵树，根桥定时发送配置BPDU，非根桥接收配置BPDU，刷新最佳BPDU并转发。这里的最佳BPDU指的是当前根桥所发送的BPDU。如果接收到了下级BPDU（新接入的设备会发送BPDU，但该设备的BID比当前根桥大），接收到该下级BPDU的设备将会向新接入的设备发送自己存储的最佳BPDU，以告知其当前网络中根桥；如果接收到的BPDU更优，将会重新计算生成树拓扑。当非根桥在离上一次接收到最佳BPDU最长寿命（Max Age，默认20s）后还没有接收到最佳BPDU的时候，该端口将进入监听状态，该设备将产生TCN BPDU，并从根端口转发出去，从指定端口接收到TCN BPDU的上级设备将发送确认，然后再向上级设备发送TCN BPDU，此过程持续到根桥为止，然后根桥在其后发送的配置BPDU中将携带标记表明拓扑已发生变化，网络中的所有设备接收到后将MAC表项的刷新时间从300s缩短为15s。整个收敛的时间为50s左右。
图——最小生成树
最小生成树生成树是啥？包含图中全部顶点的一个极小的联通子图。n个顶点，n-1条边最小生成树（最小代价树）带权的连通图，找到各边权值之和最小的对于一个带权的无向图G=(V,E)，生成树不同，每棵树的权也可能不同。设R为... 查看详情
图——生成树和最小生成树(概念解析)
...opyright(c)2015,烟台大学计算机学院*Allrightresvered.*文件名称:生成树和最小生成树*作者:郑兆涵*图——生成树和最小生成树*/1.生成树的概念一个连同图的生成树是该连通图的一个极小连同子图,它含有图中全部顶点,但只有构成一棵树... 查看详情
最小生成树杂题
这里谈一下最小生成树生成树的概念：连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树。生成树是连通图的极小连通子图。所谓极小是指：若在树中任意增加一条边，则将出现一个回路；若去掉一条... 查看详情
最小生成树
最小生成树Prim时间复杂度O(n2)蓝白点思想，蓝点代表为纳入最小生成树的点，白点代表已纳入的点。初始化所有点到最小生成树的距离；（极大值）选择一个点作为树的根节点；（没有要求的话，一般选择第一个点）枚举该点出... 查看详情
图论之最小生成树最小生成树专题
占坑 查看详情
最小生成树模板题p1692(代码片段)
...向简单图，请你完成下列任务：任务1、求边权和最小的生成树（最小生成树）任务2、求边权和最大的生成树（最大生成树）任务3、求最大边最小的生成树（瓶颈生成树）任务4、求最小边最大的生成树（瓶颈生成树）Input第一行... 查看详情
生成树问题
最小瓶颈生成树：(给出加权无向图，求一棵生成树，是的最大边权尽量小) 可以从一个空树开始，按照权值从小到大，依次加入各条边，则图第一次连通的时候，改图的最小生成树就是原图的最小瓶颈生成树。 这一过... 查看详情
luogu4234最小差值生成树
题目大意 在一个带权无向图中，它的最小差值生成树为最大边与最小边差值最小的生成树。求一个图的最小差值生成树。题解30分解法 引理1最小生成树的最大边的边权是所有生成树中最大边边权中的最小值。 证明：... 查看详情
次最小生成树模版
所谓次小生成树，顾名思义就是从生成树中取出的第二小的生成树。我们在前面已经说过最小生成树的概念及代码实现了，所以接下来要说的次小生成树应该比较简单理解了。求次小生成树的两种方法1：首先求出最小生成树T，... 查看详情
生成树
生成树顾名思义是对原图提取一些边来生成一棵树。例题：CF840BLehaandanothergameaboutgraph题解 查看详情
最小生成树
一、定义1、生成树在一个无向连通图中，如果存在一个连通子图包含原图中的所有结点和部分边，且这个子图不存在回路，那么该子图被称为原图的一棵生成树。2、最小生成树所有生成树中，边权和最小的那一棵（或那几棵）... 查看详情
[kuangbin带你飞]专题六最小生成树(代码片段)
首先介绍一下最小生成树的基本知识吧。 最小生成树（MinimumSpanningTree，MST）：或者称为最小代价树Minimum-costSpanningTree:对无向连通图的生成树，各边的权值总和称为生成树的权，权最小的生成树称为最小生成树。 构成生... 查看详情
11.5最小生成树(minimumspanningtrees)
11.5最小生成树(MinimumSpanningTrees)对加权图求使得权值和最小的生成树，即为最小生成树，基于以点为基准和以边为基准，有两种求最小生成树的方法:Prim算法和Kruskal最小生成树的具体算法实现 查看详情
图的最小生成树
一个有n个顶点的连通图法生成树是原图的极小连通子图，它包含原图中所有的n个顶点，并且具有保持图连通的最小的边。根据生成树的定义，具有n个顶点的无向连通图不管它的生成树是怎么样的，它有且仅有n-1条边。如果一个... 查看详情
（最小生成树/最小瓶颈生成树）2017武汉现场赛-wifirelay
...网络的覆盖半径最小是多少 分析：看起来是像是最小生成树，这里是是求生成树中最长的边最短，就是最小瓶颈生成树。可以证明最小瓶颈生成树就是最小生成树，详细看刘汝佳《算法入门经典训练指南》343页。当时现场的... 查看详情
图的最小生成树（普利姆prim算法）(代码片段)
什么是生成树呢？一个连通图的生成树是指一个极小连通子图， 它含有图中的全部顶点，但只有足以构成一棵树的n-1条边。什么是最小生成树？在一个连通图的所有生成树中，各边的代价之和最小的那棵生成树称为该连通图... 查看详情
最小生成树mst算法（primkruskal）
最小生成树MST（MinimumSpanningTree）(1)概念一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图连通的最少的边，所谓一个带权图的最小生成树，就是原图中边的权值最小的生成树，... 查看详情
lightoj1029最小生成树+最大生成树
...大代价和最小代价的平均值为多少。分析，即求一次最大生成树，一次最小生成树1/*Whenallelseislostthefuturestillremains.*/2#definerep(X,Y,Z)for(intX=(Y);X<(Z);X++)3#definedrep(X,Y,Z)for(intX=(Y);X&g 查看详情