有关树的算法

有关图的算法

最小生成树算法：

普利姆最小生成树

             

克鲁斯卡尔最小生成树

拓扑排序：

AOV网：定点表示活动(或任务)，有向边表示活动(或任务)之间的先后关系的有向图
拓扑排序：把AOV网中的所有顶点拍成一个线性序列，满足若AOV网中存在边<Vi, Vj>,则在该序列中，Vi必位于Vj之前。，构造AOV网的拓扑序列的操作叫拓扑排序

对于存在回路的网，就无法找到其顶点的拓扑排序
拓扑排序算法思想：
1.在AOV网中选择一个入度为0的顶点并输出该顶点
2.从AOV网中删除该顶点及其所有出边
3.执行1、2，直至所有顶点已输出或网中剩余顶点入度均不为0.这说明网中存在回路，无法拓扑排序

 

关键路径：

在AOE网中，有写活动可以并行进行，因此完成整个工程的最短时间是从源点到汇点的最长路径。路径长度等于路径上各边的权之和。这条具有最大长度的路径成为关键路径；
关键活动：即不按期完成就会影响工程完成时间的活动。
关键路径上的所有活动都是关键活动

求关键路径的基本步骤：
1.对AOE网进行拓扑排序，按顶点的拓扑序列求出各事件的最早发生时间ve。若网中有回路，则终止算法
2.按拓扑序列的逆序列求出各顶点事件的最迟发生时间vl
3.根据ve和vl的值，求出各活动ai的最早开始时间e(i)与最迟开始时间l(i)。若e(i)=l(i)，则ai是关键路径
 

最短路径问题：

无权图最短路径问题：
设初始顶点为S，Di为S到顶点vi的最短路径值，在初始状态下，对于初始顶点S，设Ds=0；对于其他顶点Di=-1
1.访问初始顶点S，令Ds=0
2.寻找S出发、最短路径为1的顶点
3.寻找从S出发，最短路径为3的顶点
重复以上步骤找到最短路径，显然与按层次进行的图的广度优先遍历次序是一致的
      

正权最短路径问题(迪杰斯特拉算法)