(相关资料图)

1、 最小树形图，就是给有向带权图中指定一个特殊的点root，求一棵以root为根的有向生成树T，并且T中所有边的总权值最小。

2、 最小树形图的第一个算法是1965年朱永津和刘振宏提出的复杂度为O(VE)的算法。