数据结构和算法(十二)--最小生成树

一、最小生成树

1、最小生成树

    定义：图的生成树是它的一颗含有其所有顶点的无环连通子图，一副加权无向图的最小生成树它的一颗权值（树中所有边的权重之和）最小的生成树。

    约定：只考虑连通图。最小生成树的定义说明它只能存在于连通图中，如果图不是连通的，那么分别计算每个连通图子图的最小生成树，合并到一起称为最小生成森林。

    所有边的权重都各不相同。如果不同的边权重可以相同，那么一副图的最小生成树就可能不唯一了，虽然我们的算法可以处理这种情况，但为了好理解，我们约定所有边的权重都各不相同。

2、最小生成树原理

2.1、树的性质

1、用一条边连接树中的任意两个顶点都会产生一个新的环；

2、从树中删除任意一条边，将会得到两颗独立的树；

2.2、切分定理

  要从一副连通图中找出该图 最小生成树，需要通过切分定理完成。

切分：将图中所有顶点按照某些规则分为两个非空且没有交集的集合。

横切边：连接两个属于不同集合的顶点的边称为横切边。

例：将下图的顶点切分为两个集合，灰色顶点属于一个集合，白色顶点属于另外一个集合。

切分定理：在一副加权图中，给定任意的切分，它的横切边中的权重最小者必然属于图中的最小生成树。

注意：一次切分产生的多个横切边中，权重最小的边不一定是所有横切边中唯一属于图的最小生成树的边。

3、贪心算法

    贪心算法是计算图的最小生成树的基础算法，它的基本原理就是切分定理，使用切分定理找到最小生成树的一条边，不断的重复查到最小生成树的所有边。如果图有V个边，那么需要找到V-1条边，就可以表示该图的最小生成树。

计算图的最小生成树的算法有很多种，但是这些算法都可以看做是贪心算法的一种特殊情况，这些算法的不同之处在于保存切分和判定权重最小的横切边的方式。

4、Prim算法

数据结构和算法(一)

数据结构--栈、队列、链表、散列表、排序二叉树

数据结构和算法(十一)--图

再小的努力，乘以365都很明显！
每天⽤⼼记录⼀点点。内容也许不重要，但习惯很重要！
一个程序员最重要的能力是：写出高质量的代码！！
有道无术，术尚可求也，有术无道，止于术。
无论你是年轻还是年长，所有程序员都需要记住：时刻努力学习新技术，否则就会被时代抛弃！