首页 > 代码库 > 算法8-2:最小生成树贪婪算法

算法8-2:最小生成树贪婪算法

为了简化问题,我们需要作出一些假设。假设图中每条边的权重都是不一样的,假设整个图是连通的。这样假设的目的就是让最小生成树的计算结果是唯一的。


图的切割


介绍算法之前,需要先了解图的切割。图的切割就是将顶点分割成两部分,切到的边称之为交叉边。下图红色的先就是交叉边。



在最小生成树中,无论如何切割,最小生成树总是从交叉边中选择最小的一条边。下图中红色的粗边就是最小生成树上的边。



算法步骤


贪婪算法的步骤如下:

  1. 所有的边在一开始都是灰色的,最小生成树的边是黑色的。

  2. 任意选择一种切割方法,只要不切割到黑色的边即可。从被切割到的边中选择最短的一条边标记成黑色,表示这条边属于最小生成树

  3. 重复步骤2,直到黑色的边连接所有的顶点为止


贪婪算法的性能比较差,后续将会介绍kruskai算法、prim算法和boruvka,因此这里就不编写代码了。