造价通
反馈
取消

热门搜词

造价通
取消 发送 反馈意见

建设工程知识

最小支撑树结构介绍

2022/07/16240 作者：佚名
导读：最小支撑树生成树 由图遍历的过程中经过的边加上图的所有顶点所构成的子图。 最小支撑树生成树的特点 （1）n个顶点的连通子图的生成树是一个极小连通子图，它包含图中所有顶点和n-1条边（但有n-1条边的图不一定是生成树）。 （2）生成树中任意两个顶点间的路径是唯一的。 最小支撑树树的权 生成树T各边的权值总和称为该树的权。 最小支撑树最小生成树 将权最小的生成树称为图的最小生成树。 Krusal算法和

最小支撑树生成树

由图遍历的过程中经过的边加上图的所有顶点所构成的子图。

最小支撑树生成树的特点

（1）n个顶点的连通子图的生成树是一个极小连通子图，它包含图中所有顶点和n-1条边（但有n-1条边的图不一定是生成树）。

（2）生成树中任意两个顶点间的路径是唯一的。

最小支撑树树的权

生成树T各边的权值总和称为该树的权。

最小支撑树最小生成树

将权最小的生成树称为图的最小生成树。

Krusal算法和Prim算法是两个构造最小生成树的著名算法。

*文章为作者独立观点，不代表造价通立场，除来源是“造价通”外。
关注微信公众号造价通（zjtcn_Largedata），获取建设行业第一手资讯

热门推荐

相关阅读