专栏首页ICSOC.TECH不求甚解之 Spanning Tree

不求甚解之 Spanning Tree

最近在阅读 USB4 的标准,文档中多次提到 Spanning Tree,于是网上搜了搜,大概有了些概念,写下来促进理解。

Spanning Tree(生成树) 在数学上属于 Graph Theory(图论)的范畴,在应用上属于数据结构和算法。

首先从 Graph(图) 的概念入手,简单来说,

  • 一个图包含若干 Vertices(顶点,单数 Vertex) 和若干 Edges(边)。
  • 顶点的 Degree(度)是指以该顶点为端点的边的数量。有方向的边叫做 Arc (有向边,弧)。
  • 如果一个图是由顶点和有向边组成的,就叫做 Directed Graph(有向图)。

概念有点多,还是回到我们关注的生成树。

一个生成树是一个图的子集,它包含了最少数量的边以连接该图中所有的顶点。

如下图所示。

从上图可以对 Spanning Tree 有一个非常直观和浅显的了解。

不过深入的看,一个图的生成树有一些严谨的性质。

  • 一个连通图可以有不止一个生成树;
  • 一个图的所有可能的生成树,都有相同数量的边和顶点;
  • 生成树不会有任何环(cycle,loop);
  • 在一个生成树中删除一个边,会导致该图不连通;
  • 在一个生成树中增加一个边,会创建一个环;
  • 生成树有 n-1 条边,n 是顶点数量;

性质也是一大把,看的人头晕.

在我们能够接触到的实际应用中,比较典型的感觉还是在一个 Connected Weighted Graph(连通赋权图)中寻找它的 Minimum Spanning Tree (MST,最小权值生成树)。例如路径规划、人员分派等应用。

构造最小生成树有两种常用算法。

  • Kruskal's Algorithm
  • Prim's Algorithm

有了上面的基础,在文档中再遇到 Spanning Tree 这个词汇的时候,脑子里大概就会有个基本的生成树的拓扑结构,有助于更好的理解上下文。

本文分享自微信公众号 - icsoc(ic-soc),作者:韩京飞

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Verilog Task Concurrent Activation

    最近做一个模块级的仿真,需要在两个过程中反复调用同一个 Task。这种场景还是比较常见的,比如一个过程作为普通的配置过程,一个作为中断服务过程,这个 Task ...

    icsoc
  • Pin/PAD Design In SoC

    已经有很长一段时间不做 SoC Integration 方面的工作了,这篇是芯片 IO 相关的一些设计经验总结,主要是方便自己将来重新拾起,同时也希望能和大家分...

    icsoc
  • 双屏工作的小工具

    最近公司逐步给大家的电脑升级成了双显示器,一只眼睛看代码、一只眼睛看波形,效率果然提高不少

    icsoc
  • 干货 | 携程机票日志追踪系统架构演进

    机票业务看起来简单,实际上整个流程的处理链条很长,调用关系也非常复杂,上下游涉及的各类日志种类约60个,每种日志都有独立格式和请求/响应报文,日生产的日志数据量...

    携程技术
  • 信息化服务范围

    网站设计要能充分吸引访问者的注意力,让访问者产生视觉上的愉悦感。因此在网页创作的时候就必须将网站的整体设计与网页设计的相关原理紧密结合起来。网站设计是将策划案中...

    貟王軍
  • 语音如何转文字,学会这个轻松搞定

    语音如何转文字?这是很多人都会考虑的问题,特别是在工作中遇到这样的问题该怎么办呢?今天就来为大家介绍一下解决的方法吧,一起来看看吧。

    高效办公
  • HashMap面试题,看这一篇就够了!

    在后端的日常开发工作中,集合是使用频率相当高的一个工具,而其中的HashMap,则更是我们用以处理业务逻辑的好帮手,同时HashMap的底层实现和原理,也成了面...

    天之痕苏
  • ReactiveCocoa(二)

    Scott_Mr
  • 产品经理眼中比较理想的WEB扫描器

    摘要 漏洞扫描器,也叫VA(Vulnerability Assessment)漏洞评估或者VM(Vulnerability Management)漏洞管理,一直...

    FB客服
  • Spread for Windows Forms高级主题(8)---通过暂停布局提高性能

    一种改善控件性能的方法是,当需要对许多单元格进行变动时,可以先保持或挂起重画,直到所有的变动都完成时再进行。通过在对单元格修改和重算时保持重画(挂起布局),然后...

    葡萄城控件

扫码关注云+社区

领取腾讯云代金券