31.4 图论

（最小树问题）连通且不含圈的无向图称为树。若图 G=(V,E)的生成子图是一棵树，则该树称为 G 的生成树。一棵生成树所有树枝上的权和，称为这棵生成树的权。具有最小权的生成树称为最小生成树（简称最小树）。寻找生成树有破圈法和避圈法两种。

用破圈法求解图的一个支撑树，即任意找到一个圈，通过去除这个圈的任意一边，使之不再构成圈；继续寻找下一

31.4 图论
 
（最小树问题）连通且不含圈的无向图称为树。若图 G=(V,E)的生成子图是一棵树，则该树称为 G 的生成树。一棵生成树所有树枝上的权和，称为这棵生成树的权。具有最小权的生成树称为最小生成树（简称最小树）。寻找生成树有破圈法和避圈法两种。
 
用破圈法求解图的一个支撑树，即任意找到一个圈，通过去除这个圈的任意一边，使之不再构成圈；继续寻找下一个圈，按照同样的办法，进行破圈，直至图中不再存在任何圈，此时所得的图就是原图的支撑树，如下图。

用避圈法求解图的一个支撑树，即从起始点开始，选择边，当再选择其他边构成圈时，就放弃该边；继续选择下一条边，按照同样的方法，直至图中所有边都被遍历一遍而又没有构成圈为止，如下图。

相应的寻找最小支撑树也可以采用上述两种方法。破圈法，即任取一个圈，从圈中去掉一条权最大的边。在余下的图中，重复这个步骤，一直到一个不含圈的图为止，这时的图便是最小树，如下图。


避圈法，即开始选一条权最小的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈，其最终的结果破圈法得到的结果是一样的，这也说明，不同的方法所获得的最小支撑树大小是一样的。