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

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

在这里插入图片描述

最短路径生成树

最短路径生成树

最小生成树

在这里插入图片描述

这时候大家会发现，最短路径生成树不就是求完最短路之后，路径所构成的树吗，其实就是这样的。但是这里要明白一点，最短路径生树不唯一。我们举一个最简单的例子，如下图：

在这里插入图片描述

只选 2-3权值的边构成一颗最短路径生成树，之选2 5构成一颗最短路径生成树。 最短路径生树的详解：戳这里 最小生成树的详解：戳这里 生成树相关：戳这里