某开发区有新建的5个工厂,相互之间的距离由下列矩阵表示(单位为千米)现要架设供电线路。请找出最短的供电线路铺设方,并算出该方案的

某开发区有新建的5个工厂,相互之间的距离由下列矩阵表示(单位为千米)

现要架设供电线路。请找出最短的供电线路铺设方,并算出该方案的线路长度。

(1)先画出5个工厂的相互距离情况如答34图-1所示

(2)根据Kruskal算法,可得答34图-1的最小生成树T如答34图-2所示

此即最短的供电线路铺设方案。
(3)可以算出答34图-2所示的线路长度为W(T)=4+5+7+6=22(千米)