最小生成树和最短路径的区别（最小生成树）

大家好，我是小十，我来为大家解答以上问题。最小生成树和最短路径的区别，最小生成树很多人还不知道，现在让我们一起来看看吧！

1、

1、最小生成树

2、　　对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权，记作：

3、　　这里:

4、　　TE表示T的边集

5、　　w(u，v)表示边(u，v)的权。

6、　　权最小的生成树称为G的最小生成树(Minimum Spanning Tree)。最小生成树可简记为MST。

7、最小生成树性质：设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中一条“一个端点在U中(例如：u∈U)，另一个端点不在U中的边(例如：v∈V-U)，且(u，v)具有最小权值，则一定存在G的一棵最小生成树包括此边(u，v)。

本文到此讲解完毕了，希望对大家有帮助。

　　免责声明：本文由用户上传，与本网站立场无关。财经信息仅供读者参考，并不构成投资建议。投资者据此操作，风险自担。 如有侵权请联系删除！