7.3最小生成树 定义710:设G(V,E,w)是带权连通简单图,w是 从E到实数集的函数。又设T是G的一棵生成 树,T中所有枝的权之和称为T的权记为W(T)。 具有权minW(T)的生成树称为最小生成树。 这个问题是具有实际意义的。例如G的顶点 表示城市,G的边表示城市间的道路边的权 表示对应道路的长度,现在沿着道路架设通讯 线路,将这些城市联系起来,要求架设的线路 最短,这个问题就是求一棵最小生成树的问题7.3最小生成树 定义7.10:设G(V,E,w)是带权连通简单图, w是 从E到实数集的函数。又设T是G的一棵生成 树,T中所有枝的权之和称为T的权,记为W(T)。 具有权 minTW(T)的生成树称为最小生成树。 这个问题是具有实际意义的。例如G的顶点 表示城市, G的边表示城市间的道路,边的权 表示对应道路的长度, 现在沿着道路架设通讯 线路, 将这些城市联系起来, 要求架设的线路 最短,这个问题就是求一棵最小生成树的问题