破圈法的证明 看不懂 求讲解 谢谢 考试题

Answer 1

破圈法：寻找一个连通图的最小支撑树（最小部分树、最小生成树），也就是BST的一种方法。Kruskal,Prim也是求BST的算法。
　　另外有两种方法，一种是破圈法，另一种是避圈法。
　　破圈法是“见圈破圈”，即如果看到图中有一个圈，就将这个圈的边去掉一条，直至图中再无一圈为止。（其中破圈法的" 圈"指的是回路）
　　避圈法则采取先将图中的点都取出来，然后，逐渐向上面添边，并保证后添入的边不与以前添上的边构成圈就可以了，这个过程直到将边集中能加入的边（加入后不够成圈）都加完为止。
　　注：其中破圈法和避圈法的" 圈"指的是回路
---------------------
http://www.mowker.com/qkdq.htm