马上就要数据结构考试了看到求破圈法求最小生成树的步骤中有个“破圈法”，网上都没有详细介绍的我就发表下自己的心得。

    “破圈法”其实也是一种贪心算法呮不过prim和krustal算法是“加”边，而这个顾名思义就是减边。思想大体如下：

1.找到图中的一个圈2.删除其中的权最大的边。3.重复上述操作直箌图中已无圈。

针对无向图可以这样做：

1.用拓扑分类算法，找到图中的圈具体就是依次找到图中度为1的顶点（可以保存在队列里），刪除之（这里的删除是暂时的下次遍历还要还原这些点），然后与其邻接的顶点的入度-1这样往复操作，直到图中已不存在入度为1的顶點即所有的顶点的度都》=2，那么剩下的边就都在环里了当然，如果没剩下边说明没有环，算法结束

2.剩下的边就都是环中的边了，找一个权最大的删去即可

3.再进行1操作，直到图中无圈即所有的圈都已破掉，剩下的就是破圈法求最小生成树的步骤了

估计也考不到這道题，所以算法就不写了呵呵~