避圈法求最小生成树

三、避圈法求最小生成树

所谓避圈法求最小生成树，即首先将连通图的边按权数从小到大的顺序，先画权数最小的边，在此基础上，依次类推，直到权数最大的边为止.

例4 （管道铺设）某高校锅炉房到各座楼的距离如图

9-29所示，试设计铺设暖气管道的路线，使管道总长度最小（单位：m）.

解 首先根据题意将上述图形改为网络图，并将锅炉房记为顶点，其他的地点依次按标号1，2，…，10记为顶点v1，v2，…，v10，由此得到图9-30.

然后将图中的各边按从小到大的顺序排列：

再将边按从小到大的顺序依次添加到图中去，注意，若某边添加到图中和前面已添加的边构成圈时，该边不能加入到图中，则依次得到图9-31（a），图9-31（b），图9-31（c）：

以此类推，最后得到网络如图9-32所示.

按如图所示铺设管道，所需管线最短，总长为1540 m.