《现代通信网》课件K方法求最小支撑树 (2).ppt

1、 例例8-38-3要建设连接如图要建设连接如图8-138-13所示的五个城所示的五个城镇的线路网，图中所标权值为两城镇之间的镇的线路网，图中所标权值为两城镇之间的距离，请用距离，请用K K方法找出连接这五个城镇线路费方法找出连接这五个城镇线路费用最小的网路结构图（设线路费用与距离成用最小的网路结构图（设线路费用与距离成正比）。正比）。6.4148512118.51063v2图图8-13 8-13 五个城镇的地图五个城镇的地图v1v3v4v5K0K0：将城镇之间的距离按非减次序排列，如下表。：将城镇之间的距离按非减次序排列，如下表。6.4148512118.51063v2v1v3v4v5第三章第

2、三章 通信网路设计基础通信网路设计基础图图8-13 8-13 五个城镇的地图五个城镇的地图例：下图是一个有例：下图是一个有7 7个节点的图个节点的图G G（V V，E E），），各节点之间的边及权值如图所示，试求这个各节点之间的边及权值如图所示，试求这个图的最小支撑树，画出图并求出其长度。图的最小支撑树，画出图并求出其长度。（V1V1，V2V2），权值为），权值为1 1；（V1V1，V3V3），权值为），权值为2 2，与已选边没有形成回路；，与已选边没有形成回路；（V3V3，V5V5），权值为），权值为4 4，与已选边没有形成回路；，与已选边没有形成回路；（V5V5，V6V6），权值为），权值为4 4，与已选边没有形成回路；，与已选边没有形成回路；（V1V1，V7V7），权值为），权值为4 4，与已选边没有形成回路；，与已选边没有形成回路；（V1V1，V4V4），权值为），权值为5 5，与已选边没有形成回路；，与已选边没有形成回路；至此已选够至此已选够n-1=6n-1=6条边，形成一棵最小支条边，形成一棵最小支撑树，如图所示。撑树，如图所示。最小支撑树长度最小支撑树长度=1+2+4+4+4+5=20=1+2+4+4+4+5=20