图的深度优先遍历和广度优先遍历、最小生成树、最短路径、拓扑排序、关键路径_最小生成树深度优先遍历

一、图的遍历

         图的深度优先遍历（DFS）：他的思想是：首先访问V节点，然后访问和V邻近的未被访问过的节点W，然后访问和W邻近的未被访问过的节点，以此类推；当后续的节点周围没有访问过的节点的时候，那么就依次退回之前访问的节点，直到找到周围还有未被访问过的节点，然后接着访问这些未被访问的节点就好了，直到全部的节点全部访问完。

        图的广度优先遍历（BFS）：首先访问起始节点V，然后访问V邻近的全部节点w1,w2....wn，然后依次访问w1,w2....wn的全部邻近节点，以此类即可。

二、最小生成树

        最小生成树是针对无向图的，有两种算法，一种是Prime算法，一种是kruskal算法，两者的区别在于，Prime算法针对于顶点来确定最小生成树，而kruskal算法是针对边来确定最小生成树的。（生成树是没有环的。）

        Primes算法的思想：首先从图中选出一个顶点，把它当做一棵树，然后观察这个顶点周围的边，选择权重最小的边所连接的未并入的顶点加入生成树中，这下有两个成员了，然后再观察这个树所延展的所有候选边（注意候选边是不可以选择让树变成环的边，哪怕这个边的权值很小），将最短的边所连接的未加入的顶点加入就好了。最后将所有的顶点加入就形成了最小生成树了。

        kruskal的算法思想：首先在图中不断地选择权值最小的边，但前提是选择的边不能使得最小生成树变成了环，直到选择的边将所有的顶点连接起来就好了。（最常用的手工方式）

三、最短路径

        最短路径是针对有向图的，也有两种算法，一个是迪杰斯特拉算法，一个是弗洛伊德算法（一般是四阶），迪杰斯特拉算法的特点是求出的是某一个固定顶点到其他顶点的最短距离，注意这个顶点是固定的；弗洛伊德算法的特点是求出了任意一对顶点的之间的最短路径。

        迪杰斯特拉算法的思想：这个算法需要用到三个辅助数组 dist[]、path[]、set[]。

        首先dist[]数组是用来记录固定顶点V0到其他顶点的最短路径长度；path[]数组是用来记录顶点V0到其他顶点最短路径中，终点顶点（即其他顶点）前一个顶点；set[]数组是用来记录其他顶点是否进入了最短路径之中，如果进入了，那么设置为1，如果没有进入，那么设置为0。

        要点：1. path[]是随着dist[]数组变化的

                   2. 更新后，观看set[]数组中为0且dist[]不为无穷大的顶点，在这里面找到数值最小的顶点加入就好了。

                   3. 起点到中间节点之间可以是路径，但是中间节点到终点之间一定要是条边。

        弗洛伊德算法的思想：这个算法需要用到两个数组 A[]数组和path[]，这两个数组根据中间节点的变化而变化，A[]记录当前已经求得的任意两个顶点最短路径长度，path[]记录是任意两个顶点间最短路径的中间节点，如果两个顶点之间没有路径，那么path记录的就是-1。

        弗洛伊德算法的原理有点复杂：首先他要求得是所有任意两条边之间的最短路径，因为是有向图，所有有向路径有两倍的数量，比如0-1，1-0这样的，那么有向最短路径之间可能会有中间节点，那那些中间节点会使得上述的有向路径距离最短呢，所以就需要依次的将各个顶点当做是中间节点，对这些有向路径进行迭代，看看那个中间节点造成的有向路径是最短的，这样就好了。

        要点：

        1. 如果确定了中间节点V，那么选择有向路径的时候，可以跳过那些包含有V的有向路径，因为结果肯定是不会变化的，这样节省了计算的时间。

四、拓扑排序

        AOV网（有向），这个是活动在顶点上的网，即顶点表示的是活动，而边界表示的是活动的次序。

        一个有向图的拓扑排序可能是不唯一的！！！

        拓扑排序：从有向图中选择一个没有入度的顶点，删除这个顶点并记录，然后删除链接这个顶点所有的边，然后再找到一个入度为0的顶点，但是这个时候可能会出现两个入度为0的顶点，那么就随机选择就好（这就是为什么拓扑排序可能不唯一。）

        逆拓扑排序：方法和上面差不多，只不过将上面的入度变成了出度而已，最后得出的拓扑序列就是逆拓扑序列。

五、关键路径

        AOE网是顶点是事件，而边界表示活动，也表示活动持续的时间。AOE表示的是活动在边上的网。

        一个有向图的关键路径可能不是唯一的！！！

        注意四个关键词，事件最早发生时间，事件最迟发生时间，活动最早发生时间，活动最迟发生时间。

        事件最早时间步骤：先求出拓扑排序，然后按照拓扑排序的顺序来确定事件的最早发生时间，在顶点岔路口的时候，即两个事件同时指向同一个事件时，选择使得总时间最长的那条路（向后选），这样才能保证在到达该顶点的时候使得之前的顶点全部制定完毕，以此总时间作为该顶点事件的最早发生时间。然后按照上述的原则完成事件最早时间的统计。

        事件最晚时间步骤：先求出逆拓扑序列，按照逆拓扑序列的顺序来确定事件最晚发生时间，此刻最后一个顶点的最晚发生时间就是等于最后一个顶点的最早发生时间（这是关键）。然后在遇到顶点岔路的时候，即顶点A和顶点B同时被顶点C指向着，因为是逆向求所以事件C的最晚发生时间需要顶点A和顶点B的结合而确定，这个时候选择A,B顶点扣除路径上权重后最小的值为C顶点的最晚事件（向前选），这样才能保证C按时送到。最后按照上述的操作就可以求出最终的时间最晚时间步骤了。

        而活动的最早发生时间 = 射出这条边的事件顶点的最早发生时间

        而活动的最晚发生时间 = 活动指向的事件顶点的最晚发生时间 - 活动的权重

        然后在两个活动表中，找出最早和最晚时间都相同的活动，即为关键活动，这些活动组成的路径即为关键路径。

注意：一个有向图可能有多条关键路径，这些关键路径的长度是相同的且为最长的，如果想要工期加快的话，必须加快包含着所有关键路径任意一个活若干个活动的集合，这样才可以是的整个工期加快。比如关键路径A,B,C加快a1,b3,c5这样的组合才可以使得工期加快。