|
|
知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用算法 > 常用算法 >
|
|
相关知识点：32个
|
|
|
|
|
|
|
|
|
设图G=（V，E）是一个连通图，如果其子图是一棵包含G的所有顶点的树，则该子图称为G的生成树（Spanning Tree）。
|
|
|
|
当从图G中任一顶点出发遍历该图时，会将边集E（G）分为两个集合A（G）和B（G）。其中A（G）是遍历时所经过的边的集合，B（G）是遍历时未经过的边的集合。显然，G1=（V，A）是图G的子图，称子图G1为连通图G的生成树。下图所示的是图及其生成树。
|
|
|
|
|
|
|
|
对于有n个顶点的连通图，至少有n-1条边，而生成树中恰好有n-1条边，所以连通图的生成树是该图的极小连通子图。若在图的生成树中任意加一条边，则必然形成回路。
|
|
|
|
图的生成树不是唯一的。从不同的顶点出发，选择不同的存储方式和遍历方式，可以得到不同的生成树。对于非连通图而言，每个连通分量中的顶点集和遍历时走过的边集一起构成若干棵生成树，把它们称为非连通图的生成树森林。
|
|
|
|
|
|
对于连通网来说，边是带权值的，生成树的各边也带权值，于是就把生成树各边的权值总和称为生成树的权，把权值最小的生成树称为最小生成树。求解最小生成树有许多实际的应用。普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法是两种常用的求最小生成树的算法。
|
|
|
|
|
|
假设N=（V，E）是连通网，TE是N上最小生成树中边的集合。算法从顶点集合U=｛u0｝（u0∈V）、边的集合TE=｛｝开始，重复执行下述操作：在所有u∈U，ν∈V-U的边（u，ν）∈E中找一条代价最小的边（u0，ν0），把这条边并入集合TE，同时将ν0并入集合U，直至U=V时为止。此时TE中必有n-1条边，则T=（V，｛TE｝）为N的最小生成树。
|
|
|
|
由此可知，普里姆算法构造最小生成树的过程是以一个顶点集合U=｛u0｝作初态，不断寻找与U中顶点相邻且代价最小的边的另一个顶点，扩充U集合直至U=V时为止。
|
|
|
|
|
|
|
|
|
|
|
|
克鲁斯卡尔求最小生成树的算法思想为：假设连通网N=（V，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，｛｝），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同一连通分量上为止。
|
|
|
|
|
|
|
|
|
|
克鲁斯卡尔算法的时间复杂度为O（eloge）（e为网中的边数），与图中的顶点数无关，因此该算法适合于求边稀疏的网的最小生成树。
|
|
|
|
|
|
|
|
在工程领域，一个大的工程项目通常被划分为许多较小的子工程（称为活动），当这些子工程都完成时，整个工程也就完成了。若以顶点表示活动，用有向边表示活动之间的优先关系，则称这样的有向图为以顶点表示活动的网（Activity On Vertex network，AOV网）。在有向网中，若从顶点νi到顶点νj有一条有向路径，则顶点νi是νj的前驱，顶点νj是νi的后继。若<νi，νj>是网中的一条弧，则顶点νi是νj的直接前驱，顶点νj是νi的直接后继。AOV网中的弧表示了活动之间的优先关系，也可以说是一种活动进行时的制约关系。
|
|
|
|
在AOV网中不应出现有向环，若存在的话，则意味着某项活动必须以自身任务的完成为先决条件，显然这是荒谬的。因此，若要检测一个工程划分后是否可行，首先就应检查对应的AOV网是否存在回路。检测的方法是对其AOV网进行拓扑排序。
|
|
|
|
|
|
拓扑排序是将AOV网中所有顶点排成一个线性序列的过程，并且该序列满足：若在AOV网中从顶点νi到νj有一条路径，则在该线性序列中，顶点νi必然在顶点νj之前。
|
|
|
|
一般情况下，假设AOV网代表一个工程计划，则AOV网的一个拓扑排序就是一个工程顺利完成的可行方案。对AOV网进行拓扑排序的方法如下：
|
|
|
|
（1）在AOV网中选择一个入度为零（没有前驱）的顶点且输出它；
|
|
|
|
|
|
（3）重复上述两步，直至网中不存在入度为零的顶点为止。
|
|
|
|
按照上述步骤进行拓扑排序的过程如下图所示，得到的拓扑序列为6，1，4，3，2，5。显然，对有向图进行拓扑排序所产生的拓扑序列有可能是多种。
|
|
|
|
|
|
|
|
执行的结果会有两种情况：一种是所有顶点已输出，此时整个拓扑排序完成，说明网中不存在回路；另一种是尚有未输出的顶点，剩余的顶点均有前驱顶点，表明网中存在回路，拓扑排序无法进行下去。
|
|
|
|
|
|
所谓单源点最短路径，是指给定带权有向图G和源点ν0，求从ν0到G中其余各顶点的最短路径。迪杰斯特拉（Dijkstra）提出了按路径长度递增的次序产生最短路径的算法，其思想是：把网中所有的顶点分成两个集合S和T，S集合的初态只包含顶点ν0，T集合的初态包含除ν0之外的所有顶点，凡以ν0为源点，已经确定了最短路径的终点并入S集合中，按各顶点与ν0间最短路径长度递增的次序，逐个把T集合中的顶点加入到S集合中去。
|
|
|
|
每次从T集合选出一个顶点u并使之并入集合S后（即ν0至u的最短路径已找出），从ν0到T集合中各顶点的路径有可能变得更短。例如，对于T集合中的某一个顶点νi来说，其已知的最短路径可能变为（ν0，…，u，νi），其中的…仅包含S中的顶点。对T集合中各顶点的路径进行考查并进行必要的修改后，再从中挑选出一个路径长度最小的顶点，从T集合中删除它，同时将其并入S集合。重复该过程，就能求出源点到其余各顶点的最短路径及路径长度。
|
|
|
|
在下图所示的有向网中，用迪杰斯特拉算法求解顶点V0到达其余顶点的最短路径的过程如下表所示。
|
|
|
|
|
|
|
|
|
|
迪杰斯特拉算法求解上图（a）顶点V0到V1、V2、V3、V4、V5最短路径的过程
|
|
|
