最近在阅读 USB4 的标准,文档中多次提到 Spanning Tree,于是网上搜了搜,大概有了些概念,写下来促进理解。
Spanning Tree(生成树) 在数学上属于 Graph Theory(图论)的范畴,在应用上属于数据结构和算法。
首先从 Graph(图) 的概念入手,简单来说,
概念有点多,还是回到我们关注的生成树。
一个生成树是一个图的子集,它包含了最少数量的边以连接该图中所有的顶点。
如下图所示。
从上图可以对 Spanning Tree 有一个非常直观和浅显的了解。
不过深入的看,一个图的生成树有一些严谨的性质。
性质也是一大把,看的人头晕.
在我们能够接触到的实际应用中,比较典型的感觉还是在一个 Connected Weighted Graph(连通赋权图)中寻找它的 Minimum Spanning Tree (MST,最小权值生成树)。例如路径规划、人员分派等应用。
构造最小生成树有两种常用算法。
有了上面的基础,在文档中再遇到 Spanning Tree 这个词汇的时候,脑子里大概就会有个基本的生成树的拓扑结构,有助于更好的理解上下文。