破圈法vs避圈法

《破圈法vs避圈法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.1最小生成树最小生成树：一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图连通的最少的边，如图1.1.1所示。图1.1.1最小生成树示意图设G=(V,E)是无向连通带权图，即一个网络。E中的每一条边（v,w）的权为W(v,w)。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树上各边权的总和称为生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。1.1.1避圈法避圈法的主要思想就是：开始选一条最小权的边，以后每一步中

2、，总从与已选边不构成圈的那些未选边中，选择一条权最小的（每一步中，如果有两条或两条以上的边都是权值最小的边，则从中任选一条）。避圈法主要分为两种：Prim算法和Kruskal算法，下面分别进行介绍。1.1.1.1Prim算法设G=(V,E)是连通带权图，V={1,2,…,n}。构造G的最小生成树Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就进行如下的贪心选择：选取满足条件i∈S,j∈V–S，且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过

3、程中选取到的所有边恰好构成G的一棵最小生成树。图1.1.2显示了某一带权图。最小生成树的生成过程如下：13;c136;c464;c232;c525;c3最终得到的最小生成树如图1.1.3所示。图1.1.2带权图G图1.1.3带权图G的最小生成树示意图1.1.1.2Kruskal算法给定无向连通带权图G=(V,E),V={1,2,...,n}。Kruskal算法构造G的最小生成树的基本思想是：(1)将G的n个顶点看成n个孤立的连通分支，并将所有的边按权从小到大排序；(2)从第一条边开

4、始，依据每条边的权值递增的顺序检查每一条边，并按照下述方法连接两个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前两个不同的连通分支T1和T2的端点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接查看第k+1条边，这个过程一个进行到只剩下一个连通分支时为止。此时，已构成G的一棵最小生成树。仍以图1.1.2所示的带权图G为例说明其最小生成树的生成过程，生成过程如下所示：13;c146;c225;

5、c336;c423;c5最终得到的最小生成树和图1.1.3所示是一样的。1.1.2破圈法破圈法可以描述如下：(1)如果我们给的连通图G中没有回路，那么G本身就是一棵生成树；(2)若G中只有一个回路，则删去G的回路上的一条边（不删除结点），则产生的图仍是连通的且没有回路，则得到的子图就是图G的一棵生成树；(3)若G的回路不止一个，只要删去每一个回路上的一条边，直到G的子图是连通没有回路且与图G有一样的结点集，那么这个子图就是一棵生成树。由于我们破坏回路的方法可以不一样，所以可得到不同的生成树，但

6、是在求最小生成树的时候，为了保证求得的生成树的树权最小，那么在删去回路上的边的时候，总是在保证带权图仍连通的前提下删掉权值较大的边，保留权值较小的边。破圈法就是在带权图的回路中找出权值最大的边，将该边去掉，重复这个过程，直到图连通且没有圈为止，保留下来的边所组成的图即为最小生成树。下面仍利用图1.1.2对破圈法进行说明。首先是去除权值大的边，并且检测去除该边后整个图是否连通，对于图1.1.2来说，即第一步去掉权值为6的边，如图1.1.4所示。图1.1.4去掉权值为6的G的示意图从图中可以看出，去掉权值

7、为6的边后整个图仍是连通的。所以接下来去除权值为5的边，并且检测去除该边后图是否连通，结果如图1.1.5所示。由图可知，去掉所有权值为5的边会造成图G不连通，因此23;c5这条边是必须保留的。然后再去除权值为4的边。由于权值为1、2、3、4的边分别连接着独立的节点，故都必须保留，得到的最小生成图1.1.5去掉权值为5的G的示意图树结果与图1.1.3也是一样的。1.1.3避圈法与破圈法比较Prim算法是从空图出发，将点进行二分化，从而逐步加边得到最小生成树。它是近似求解算法，虽然对于大多数最小生成树

8、问题都能求得最优解，但相当一部分求得的是近似最优解，具体应用时不一定很方便。但是它可以看作是很多种最小树算法的概括，在理论上有一定的意义。Kruskal算法也是从空图出发。它是精确算法，即每次都能求得最优解，但对于规模较大的最小生成树问题，求解速度较慢。破圈法是从图G出发，逐步去边破圈得到最小生成树。它最适合在图上工作，当图较大时，可以几个人同时在各个子图上工作，因此破圈法在实用上是很方便的。