最小树形图的定义: 设G=(V,E)是一个有向图,如果具有下述性质: (1)G中不包含有向环 (2)存在一个顶点vi,它不是任何弧的终点,而V的其他顶点都恰好是唯一的一条弧的终点,则称G是以vi为根的树形图。 最小树形图就是有向图G=(V,E)中以vi为根的树形图中权值和最小的那个。显而易见,对于不同的vi,得到的最小树形图是不一样的,甚至有可能不存在。 1.基本算法 使用的是朱刘算法(Edmon...