零零散散学算法之详解最小生成树.doc

弱弱地问一下,最小生成树会应用到什么地方呢?为什么要找到这个最小生成树呢?
用数据结构中的话描述:要在N个城市间建立通信联络网,且连通着N个城市只需要N-1条路线,那么如何在最节省经费的前提下建立这个连通网.
明白了,原来这文章是在说怎么编程解决运筹学问题,谢谢
零零散散学算法之详解最小生成树
分类: Algorithms & Data Structure 2012-05-01 00:20 3493人阅读评论(29) 收藏举报
深入解析最小生成树
正文
       所谓最小生成树,就是在一个具有N个顶点的带权连通图G中,如果存在某个子图G',其包含了图G中的所有顶点和一部分边,且不形成回路,并且子图G'的各边权值之和最小,则称G'为图G的最小生成树。
       由定义我们可得知最小生成树的三个性质:
             •最小生成树不能有回路。
             •最小生成树可能是一个,也可能是多个。
             •最小生成树边的个数等于顶点的个数减一。
       本文将介绍两种最小生成树的算法,分别为克鲁斯卡尔算法(Kruskal Algorithm)和普利姆算法(Prim Algorithm)。
第一节克鲁斯卡尔算法(Kruskal Algorithm)
       克鲁斯卡尔算法的核心思想是:在带权连通图中,不断地在边集合中找到最小的边,如果该边满足得到最小生成树的条件,就将其构造,直到最后得到一颗最小生成树。
       克鲁斯卡尔算法的执行步骤:
       第一步:在带权连通图中,将边的权值排序;
       第二步:判断是否需要选择这条边(此时图中的边已按权值从小到大排好序)。判断的依据是边的两个顶点是否已连通,如果连通则继续下一条;如果不连通,那么就选择使其连通。
       第三步:循环第二步,直到图中所有的顶点都在同一个连通分量中,即得到最小生成树。
下面我用图示法来演示克鲁斯卡尔算法的工作流程,如下图:
首先,将图中所有的边排序(从小到大),我们将以此结果来选择。排序后各边按权值从小到大依次是:
HG < (CI=GF) < (AB=CF) < GI < (CD=HI) < (AH=BC) < DE < BH < DF
接下来,我们先选择HG边,将这两个点加入到已找到点的集合。这样图就变成了,如图
继续,这次选择边CI(当有两条边权值相等时,可随意选一条),此时需做判断。
判断法则:当将边CI加入到已找到边的集合中时,是否会形成回路?
      ,那么直接将其连通。此时,对于边的集合又要做一次判断:这两个点是否在已找到点的集合中出现过?
          ①.如果两个点都没有出现过,那么将这两个点都加入已找到点的集合中;
          ②.如果其中一个点在集合中出现过,那么将另一个没有出现过的点加入到集合中;
          ③.如果这两个点都出现过,则不用加入到集合中。
      ,不符合要求,直接进行下一次操作。
根据判断法则,不会形成回路,将点C和点I连通,并将点C和点I加入到集合中。如图:
继续,这次选择边GF,根据判断法则,不会形成回路,将点G和点F连通,并将点F加入到集合中。如图:
继续,这次选择边AB,根据判断法则,不会形成回路,将其连通,并将点A和点B加入到集合中。如图:
继续,这次选择边CF,根据判断法则,不会形成回路,将其连通,此时这两个点已经在集合中了,所以不用加入。如图:
继续,这次选择边GI,根据判断法则,会形成回路,如下图,直接进行下一次操作。
继续,这次选择边CD,根据判断法则,不会形成回路,将其连通,并将点D加入到集合中。如图:
继续,这次选择边HI,根据判断法则,会形成回路,直接进行下一次操作。
继续,这次选择边AH,根据判断法则,不会形成回路,将其连通,此时这两个点已经在集合中了,所以不用加入。
继续,这次选择边BC,根据判断法则,会形成回路,直接进行下一次操作。
继续,这次选择边DE,根据判断法则,不会形成回路,将其连通,并将点E加入到集合中。如图:
继续,这次选择边BH,根据法则,会形成回路,进行下一次操作。
最后选择边DF,根据法则,会形成回路,不将其连通,也不用加入到集合中。
好了,所有的边都遍历完成了,所有的顶点都在同一个连通分量中,我们得到了这颗最小生成树。
       通过生成的过程可以看出,能否得到最小生成树的核心问题就是上面所描述的判断法则。那么,我们如何用算法来描述判断法则呢?我认为只需要三个步骤即可:
      ⒈将某次操作选择的边XY的两个顶点X和Y和已找到