在计算机网络中，如果我们想防止环路拓扑，我们使用 STP（生成树协议）或 RSTP（快速生成协议）。我在离散数学中读到过，为了找到生成树，已经描述了两种算法，广度优先搜索算法和深度优先搜索算法。
我只是好奇 IEEE 802.1D (STP) 或 IEEE 802.1w (RSTP) 使用了哪种算法？
IEEE 802.1_ 协议是否使用 BFS 或 DFS 来查找生成树？
网络工程
生成树
网络
2021-07-18 10:18:39
1个回答
这是一个很好的问题。我并不声称有完美的答案，但似乎有两种可能的回答方式。一个是该算法是由 Radia Perlman 提出的，大约在 1984 年出版，并被 IEEE 采用/改编。二是，如果你去掉那篇论文中“扩展”中描述的任意组件，并将问题视为加权无向图，那么你就有了类似于 Bellman-Ford 算法的东西。该算法计算每个顶点的根路径成本和前身，只需要邻居的知识。因此它可以提供分布式计算，这与 Dijkstra 不同，后者需要控制手。