RSTP(快速生成树)快速生成树协议（RapidSpanningTreeProtocol，RSTP）用于在局域网中消除数据链路层物理环路，其核心是快速生成树算法。RSTP完全向下兼容STP协议，除了和传统的STP协议一样具有避免回路、动态管理冗余链路的功能外，RSTP极大的缩短了拓扑收敛时间，在理想的网络拓扑规模下，所有交换设备均支持RSTP协议且配置得当时，拓扑发生变化（链路UP/DOWN）后恢复稳定的时间可以控制在秒级，而传统的拓扑稳定且能正常工作所需时间为50秒基本配置:端口默认开启，不用配置LSW1:stpenable#开启生成树协议stpmoderstp#生成树模式改为rstpstp

作者简介：一名在校云计算网络运维学生、每天分享网络运维的学习经验、和学习笔记。  座右铭：低头赶路，敬事如仪个人主页：网络豆的主页​​​​​​目录前言一.知识点总结

目录最小生成树Prim算法实现最小生成树kruskal算法实现最小生成树最小生成树Q：什么是广度优先搜索A：一个连通图的生成树含有图中全部的顶点，并且只含尽可能少的边。若砍去它的一条边，则会使生成树变成非连通图。若给它增加一条边，则会形成图中的一条回路。对于一个带权连通无向图G=(V,E)，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同，其中边的权值之和最小的那棵生成树（构造连通网的最小代价生成树），称为G的最小生成树。通过定义不难看出，最小生成树具有以下性质：1）最小生成树不是唯一的，即最小生成树的树形不唯一，所有生成树中可能有多个最小生成树。当图G中的各边权值互不相等时，G的

图对于n个结点的图来说：无向完全图：有n（n-1）/2条边，如下：4个顶点有6条边连通图：无向图中，任意两个顶点是连通的（一个顶点不必与另一个顶点直接相连，可以通过其它顶点到达即可）最少有n-1条边；如下：4个顶点最少需要3条边才能够连通非连通图，即边数少于n-1条，最多有（n-1）*(n-2)/2条，如下：5个结点，非连通，最多有6条边连通分量：无向图中（区别于有向图）的极大连通子图，极大即要求拥有连通子图的所有边，例如，如果A1中少了a-d这条边就不是极大连通子图了强连通图：从a到b和从b到a都有路径。最少有n条边，假若少了A-D的路径，则A可以到D，但是D到不了A，就不满足条件。强连通分

文章目录虚拟源点：1146.新的开始贪心或kruskal性质：1145.北极通讯网络最小生成树与完全图：346.走廊泼水节次小生成树：1148.秘密的牛奶运输虚拟源点：1146.新的开始1146.新的开始-AcWing题库与一般的最小生成树问题不同，本题需要在建立电站的电井之间建立电网，在两个电站之间建立电网需要花费金额，可以看成一条具有权值的边但是建立电网的前提是：其中一个电井需要建立电站，建立电站也需要费用已经建立电站的两个电井之间无需建立电网，即一张电网中只需要存在一个建立电站的电井可以将建立电站也看成具有权值的边，设置虚拟源点，在第i个电井建立电站可以转换成虚拟源点与i点之间的边，权值

MSTP基本定义通过MSTP把一个交换网络划分成多个域，每个域叫做一个MST域（MSTRegion：MultipleSpanningTreeRegion）。每个域内形成多棵生成树，生成树之间彼此独立，每棵生成树叫做一个MSTI（MultipleSpanningTreeInstance）。每个实例是由一个或者多个vlan组成。mstpnetworkMSTP示意图CST：公共生成树CST（CommonSpanningTree）是连接交换网络内所有MST域的一棵生成树，如果把每个MST域看作是一个节点，CST就是这些节点通过STP或RSTP协议计算生成的一棵生成树。IST：内部生成树IST（Inte

文章目录lcaTarjan板子题：1172.祖孙询问lca或tarjan：1171.距离356.次小生成树352.闇の連鎖lcaO(mlogn)O(mlogn)O(mlogn)，n为节点数量，m为询问次数，lca是一种在线处理询问的算法自己也是自己的祖先倍增：fa(i,j)fa(i,j)fa(i,j)表示从i开始，向上走2j2^j2j步走到的点j=0，走到父节点j>0，分两步走，先走到2j−12^{j-1}2j−1步再走2j−12^{j-1}2j−1步，那么一共就会走2j2^j2j步，fa(i,j)=fa(fa(i,j−1),j−1)fa(i,j)=fa(fa(i,j-1),j-1)fa(i,

借鉴网址：​​​​​​https://blog.csdn.net/carol980206/article/details/86609249?utm_medium=distribute.pc_relevant.none-task-blog-title-3&spm=1001.2101.3001.4242姓名彭彭头实验日期2022.04.15学号实验序号10实验名称配置STP生成树协议一、实验目的及要求掌握STP的基本工作原理及配置方法，理解广播风暴的缘由二、实验环境Cisco软件、2台交换机、4台主机、直连线三、实验内容1.建立拓扑图2.配置主机：IP地址、子网掩码、网关3.配置交换机：配置STP

借鉴网址：​​​​​​https://blog.csdn.net/carol980206/article/details/86609249?utm_medium=distribute.pc_relevant.none-task-blog-title-3&spm=1001.2101.3001.4242姓名彭彭头实验日期2022.04.15学号实验序号10实验名称配置STP生成树协议一、实验目的及要求掌握STP的基本工作原理及配置方法，理解广播风暴的缘由二、实验环境Cisco软件、2台交换机、4台主机、直连线三、实验内容1.建立拓扑图2.配置主机：IP地址、子网掩码、网关3.配置交换机：配置STP

STPSTP（SpanningTreeProtocol）是生成树协议的英文缩写，可应用于计算机网络中树形拓扑结构建立，主要作用是防止网桥网络中的冗余链路形成环路工作。但某些特定因素会导致STP失败，要排除故障可能非常困难，这取决于网络设计。生成树协议适合所有厂商的网络设备，在配置上和体现功能强度上有所差别，但是在原理和应用效果是一致的基本配置:接口不用配置，默认开启LSW3:inteth0/0/1#进入接口eth0/0/1中portlink-typeaccess#可以不用配置vlan，但是access接口一定要开，不开不能通信quit#退出接口配置模式​LSW4:inteth0/0/1#进入接