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

一、有向图

定义:
有向图是一副具有方向性的图，是由一组顶点和一组有方向的边组成的，每条方向的边都连着一对有序的顶点。
出度:
由某个顶点指出的边的个数称为该顶点的出度。
入度:
指向某个顶点的边的个数称为该顶点的入度。
有向路径:
由一系列顶点组成，对于其中的每个顶点都存在一条有向边，从它指向序列中的下一个顶点。
有向环:
一条至少含有一条边，且起点和终点相同的有向路径。

一副有向图中两个顶点v和w可能存在以下四种关系:
1.没有边相连;
2.存在从v到w的边v->w;
3.存在从w到v的边w->v;
4.既存在w到v的边，也存在v到w的边，即双向连接

理解有向图是一件比较简单的，但如果要通过眼睛看出复杂有向图中的路径就不是那么容易了。

二、拓扑排序

三、加权无向图

    加权无向图是一种为每条边关联一个权重值或是成本的图模型。这种图能够自然地表示许多应用。在一副航空图中,边表示航线,权值则可以表示距离或是费用。在一副电路图中，边表示导线,权值则可能表示导线的长度即成本，或是信号通过这条先所需的时间。此时我们很容易就能想到，最小成本的问题,例如，从西安飞纽约,怎样飞才能使时间成本最低或者是金钱成本最低?

    在下图中，从顶点0到顶点4有三条路径，分别为0-2-3-4,0-2-4,0-5-3-4,那我们如果要通过那条路径到达4顶点最好呢?此时就要考虑那条路径的成本最低。

    加权无向图中的边我们就不能简单的使用v-w两个顶点表示了，而必须要给边关联一个权重值，因此我们可以使用对象来描述一条边。

四、最小生成树

1、最小生成树

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

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

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

2、最小生成树原理

2.1、树的性质

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

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

2.2、切分定理

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

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

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

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

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

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

3、贪心算法

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

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

4、Prim算法

    先学习第一种计算最小生成树的方法叫Prim算法，它的每一步都会成为一颗生成中的树添加一条边。一开始这棵树只有一个顶点，然后会向它添加V-1条边，每次总是将下一条连接树中的顶点与不在树中的顶点且权重最小的边加入到树中。

Prim算法的切分规则：把最小生成树的顶点看做是一个集合，把不在最小生成树中的顶点看做是另外一个集合。

Prim算法API设计

类名	PrimMST
构造方法	PrimMST(EdgeWeightedGraph G)：根据一副加权无向图，创建最小生成树计算对象；
成员方法	1.private void visit()：将顶点v添加到最小生成树中，并且更新数据 2.public Queue<Edge> edges()：获取最小生成树的所有边
成员变量

数据结构和算法(一)

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

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

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