最短路径生成树与最小生成树

71 阅读 0 评论 47 点赞

我是靠谱客的博主朴实火龙果，最近开发中收集的这篇文章主要介绍最短路径生成树与最小生成树，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

虽然放在一起，但是他们两个除了都是树之外没有一点关系。
最短路径生成树，就是ROOT根节点到达任意点距离最短的路径所构成的树，就是最短路径生成树。我画两个图给大家理解。在这里插入图片描述
最短路径生成树

最小生成树

这时候大家会发现，最短路径生成树不就是求完最短路之后，路径所构成的树吗，其实就是这样的。但是这里要明白一点，最短路径生树不唯一。我们举一个最简单的例子，如下图：
在这里插入图片描述
只选 2-3权值的边构成一颗最短路径生成树，之选2 5构成一颗最短路径生成树。
最短路径生树的详解：戳这里
最小生成树的详解：戳这里
生成树相关：戳这里