马上就要数据结构考试了看到求最小生成树中有个“破圈法”，网上都没有详细介绍的我就发表下自己的心得。
“破圈法”其实也是一种贪心算法只不过prim和krustal算法是“加”边，而这个顾名思义就是减边。思想大体如下：
1.找到图中的一个圈2.删除其中的权最大的边。3.重复上述操作直到图中已无圈。
針对无向图可以这样做：
1.用拓扑分类算法，找到图中的圈具体就是依次找到图中度为1的顶点（可以保存在队列里），删除之（这里的刪除是暂时的下次遍历还要还原这些点），然后与其邻接的顶点的入度-1这样往复操作，直到图中已不存在入度为1的顶点即所有的顶點的度都》=2，那么剩下的边就都在环里了当然，如果没剩下边说明没有环，算法结束
2.剩下的边就都是环中的边了，找一个权最大的刪去即可
3.再进行1操作，直到图中无圈即所有的圈都已破掉，剩下的就是最小生成树了
估计也考不到这道题，所以算法就不写了呵呵~
本文来自CSDN博客，转载请标明出处：
可用“破圈法”破圈法例题求解過程带权连通无向图的一棵最小代价生成树所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”反复执行这一步骤，直到没有圈為止
可用“破圈法”破圈法例题求解过程带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈去掉圈上权最大的邊”，反复执行这一步骤直到没有圈为止。请给出用“破圈法”破圈法例题求解过程给定的带权连通无向图的一棵最小代价生成
马上就要数据结构考试了看到求最小生成树中有个“破圈法”，网上都没有详细介绍的我就发表下自己的心得。
“破圈法”其实也是一种贪心算法只不过prim和krustal算法是“加”边，而这个顾名思义就是减边。思想大体如下：
1.找到图中的一个圈2.删除其中的权最大的边。3.重复上述操作直到图中已无圈。
針对无向图可以这样做：
1.用拓扑分类算法，找到图中的圈具体就是依次找到图中度为1的顶点（可以保存在队列里），删除之（这里的刪除是暂时的下次遍历还要还原这些点），然后与其邻接的顶点的入度-1这样往复操作，直到图中已不存在入度为1的顶点即所有的顶點的度都》=2，那么剩下的边就都在环里了当然，如果没剩下边说明没有环，算法结束
2.剩下的边就都是环中的边了，找一个权最大的刪去即可
3.再进行1操作，直到图中无圈即所有的圈都已破掉，剩下的就是最小生成树了
估计也考不到这道题，所以算法就不写了呵呵~
本文来自CSDN博客，转载请标明出处：
