图（二）

4. 最小生成树

4.1 生成树

（1）定义：所有顶点均由边连接在一起，但不存在回路的图叫该图的生成树
（2）深度优先生成树与广度优先生成树

（3）

    一个图可以有许多棵不同的生成树
    所有生成树具有以下共同特点：
           生成树的顶点个数与图的顶点个数相同
           生成树是图的极小连通子图

4.2 最小生成树

生成树的每条边上的权值之和最小。

实例：在N个城市之间修路，总路线的总和最小问题。

4.2.1 Prim方法

设N=(V,{E})是连通网，TE是N上最小生成树中边的集合：
（1）初始令U={u0},(u0属于V), TE=NULL
（2）在所有u属于U,v属于V-U的边(u,v)属于E中，找一条代价最小的边(u0,v0)
（3）将(u0,v0)并入集合TE，同时v0并入U
（4）重复上述操作直至U=V为止，则T=(V,{TE})为N的最小生成树

4.2.2 Kruskal算法

设连通网N=(V,{E})，令最小生成树
（1）初始状态为只有n个顶点而无边的非连通图T=(V,{NULL})，每个顶点自成一个连通分量
（2）在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边
（3）依此类推，直至T中所有顶点都在同一连通分量上为止

5.拓扑排序和 关键路径

5.1 拓扑排序

拓扑排序的基础：有向无环图，它是描述一项工程进度的有效工具。

5.1.1 AOV网

用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(Activity On Vertex network)，简称AOV网

5.1.2 拓扑排序算法

（1）在有向图中选一个没有前驱的顶点且输出之
（2）从图中删除该顶点和所有以它为尾的弧
（3）重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止

5.2 关键路径

在AOV网中，完成工程的最短时间：从开始点到完成点的最长路径长度——关键路径。

Ve(j)——表示事件Vj的最早发生时间
Vl(j)——表示事件Vj的最迟发生时间
e(i)——表示活动ai的最早开始时间
l(i)——表示活动ai的最迟开始时间
l(i)-e(i)——表示完成活动ai的时间余量

6. 最短路径

最短路径：路径上所有边的权值之和最小。

6.1 某顶点到其它个点的最短路径

Dijkstra算法：

（1）初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值
（2）若存在<V0,Vi>，为<V0,Vi>弧上的权值
（3）若不存在<V0,Vi>，为无穷
（4）从T中选取一个其距离值为最小的顶点W，加入S
（5）对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值
（6）重复上述步骤，直到S中包含所有顶点，即S=V为止

6.2 每对顶点之间的最短路径

Floyd算法：

（1）初始时设置一个n阶方阵，令其对角线元素为0，若存在弧<Vi,Vj>，则对应元素为权值；否则为无穷
（2）逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值
（3）所有顶点试探完毕，算法结束

http://blog.csdn.net/matrix_laboratory/article/details/11879127