最小生成路和最短路径的区别

• 文章1： https://blog.csdn.net/Ypopstar/article/details/104808116
• 文章2： https://blog.csdn.net/with_wine/article/details/113823749
• 文章3： https://www.cnblogs.com/gonghr/p/14615609.html

最小生成树

在介绍最小生成树前，先介绍一下生成树：在一张联通无向图中，我们取图上的所有点，并取最少的边将其相连使其连通生成一棵树，这个树就被称作这张图的生成树。因为树的边数一定是点数-1，所以就是取n−1条边来连通 n 个点。

那么最小生成树(Minimum Spanning Tree)，是最小权重生成树的简称。规定树的权值为树上所有边的权值和，那么它就是一张连通加权无向图中一颗权值最小的生成树，如上图。由定义可以看出，最小生成树不一定唯一。

树的一个定理

N个点用N-1条边连接成一个连通块，形成的图形只可能是树，没有别的可能（其实也就是主要在说树是不可能存在环的）。一个有N个点的图，边一定是大于等于N-1条的。图的最小生成树，就是在这些边中选择N-1条出来，连接所有的N个点。这N-1条边的边权之和是所有方案中最小的。