破圈法求最小生成树

二、破圈法求最小生成树

所谓破圈法求连通图的最小生成树，即在连通图中任意找圈，将圈中的权数最大的边去掉，重复此过程，直至该连通图变为没有圈的连通图为止.

例3 （网络架线）某社区有9幢楼房，现要宽带进社区，经测量其间道路及各道路长度如图9-24所示，各边上的数字表示距离，问如何布线才能使网络线最短？

解 要求最短路，也就是找连通图的一个最小生成树，按破圈法的基本思路，可求解如下：

第一步 在图9-24中任意找一个圈，如v1→v2→v0→v1，

去掉其中权数最大的边（v1，v2），得到图9-25；

第二步 在图9-25中任意找一个圈，如v1→v0→v8→v1，

去掉其中权数最大的边（v0，v8），得到图9-26；

第三步 在图9-26中任意找一个圈，如v0→v6→v7→v0，

去掉其中权数最大的边（v0，v7），得到图9-27.

类似地，依次去掉选中的圈中的权数最大的边v0→v6→v7→v8→v1→v0，v0→v2→v3→v0，v0→v2→v3→v4→v0，v0→v2→v3→v4→v5→v0，v0→v5→v6→v0中的权数最大的边，最后得到图9-28.

由于该连通图中已经没有圈了，所以该图是原图9-20的生成树，又由于破圈时每次去掉的都是圈中权数最大的边，因此该生成树是最小生成树，权数总和为13，即布线时所需线长为13个单位.