|
|
|
|
|
图遍历主要有广度优先遍历和深度优先遍历两种。若能够深刻理解这两种算法的含义，则有利于进一步理解二叉树及树的前序遍历和层次遍历，尤其是理解这两种遍历的非递归算法。
|
|
|
|
下面来讨论图的深度优先遍历的非递归算法。这里，我们采用邻接表存储结构，首先讨论图的深度优先遍历的递归算法，然后再讨论图的深度优先遍历的非递归算法。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
一棵生成树的代价即树上各边的代价之和，如果该生成树的代价最小，则称该树为最小生成树（也称最小代价生成树）。
|
|
|
|
求图的最小生成树有着广泛的应用价值。例如，如何在n个城市之间建立通信联络网，并且连通n个城市只需要n-1条线路，而且通信代价最少。
|
|
|
|
构造最小生成树的算法主要有Prim（普里姆）算法和Kruskal（克鲁斯卡尔）算法两种。
|
|
|
|
|
|
Prim算法用于求无向图的最小生成树。N=(V,E)是连通网，V={V1, V2, …, Vn}是网的顶点集合，E是N上最小生成树中边的集合。引入顶点集合U和边的集合TE，U的初始状态为{V1}，它存放的是当前所得到的（还未完成的）最小代价生成树上的所有顶点，TE的初始状态为Ф。在Prim算法的每一步，都从所有的边{(u,v)|v∈V-U, u∈U}中找出所有代价最小的边(u,v)，同时将v并入U，(u,v)并入集合TE，直到U=V为止。此时TE中必有n-1条边，则T=(V,TE)为N的最小生成树。
|
|
|
|
Prim算法的时间复杂度为O(n2)。它适合稠密图。
|
|
|
|
|
|
Kruskal算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。若G=(V, E)是一个连通的无向图，其中V={1,2,…,n}，引入辅助集合T，来存放当前所形成的最小生成树的所有边，其初始状态为空，则Kruskal算法是逐步给T添加不与T中的边构成回路的当前最小代价边。具体步骤如下。
|
|
|
|
|
|
|
|
|
|
（4）若(v,u)不和T中的边一起构成回路，则将边(v,u)并入T中。
|
|
|
|
（5）循环执行步骤（2）～（4），直到T中的所有顶点都在同一个连通图上且包含n-1条边为止。
|
|
|
|
若带权连通无向图G有e条边，则用Kruskal算法构造最小生成树的时间复杂度为O(elog2e)。它适用于稀疏图。
|
|
|
|
|
|
顶点活动的网（也称AOV-网）是用顶点表示活动、用弧表示活动优先关系的有向图。在网中，如果从顶点i到顶点j有一条有向路径，则称i是j的前驱，j是i的后继。若是网中的一条弧，则i是j的直接前驱，j是i的直接后继。
|
|
|
|
在AOV-网中，不应存在环，因某项活动不应以它自己为先决条件，故对给定的AOV-网，可采用对有向图构造其顶点的拓扑有序序列来监测其是否存在环。拓扑有序序列是AOV-网中的顶点所构成的有序序列T=(l,…,I,…,n)，且满足以下条件：
|
|
|
|
.AOV-网的优先关系与序列所反映的先后关系一致；
|
|
|
|
.在AOV-网中无优先关系的顶点也被赋予了一定的先后关系。
|
|
|
|
则称序列T为AOV-网的一个拓扑有序序列，对AOV-网构造它的拓扑有序序列的过程叫作拓扑排序。
|
|
|
|
若网中的所有顶点都在它的拓扑有序序列中，则该AOV-网中必定不存在环。
|
|
|
|
|
|
（1）在有向图中选择一个没有前驱（即入度为0）的顶点并输出。
|
|
|
|
|
|
（3）重复执行上述步骤（1）和（2），直到全部顶点都已输出或图中已没有无前驱的顶点。
|
|
|
|
拓扑排序方法是关键路径求解问题等的基础，同时可应用于课程计划的制订等。从拓扑排序构造的方法可见拓扑排序本质上就是图的遍历过程。
|
|
|
|
|
|
Dijkstra（迪杰斯拉特）算法和Floyd（弗洛伊德）算法为求给定带权有向图G的最短路径的两种方法，其中Dijkstra算法用于求图中某一顶点到其余顶点的最短路径，Floyd算法用于求图中每一对顶点之间的最短路径。
|
|
|
|
Dijkstra算法提出了一个按路径递增的顺序产生最短路径的算法。首先引入一个辅助向量D，它的分量D(i)表示当前所有找到的从始点V到每个终点Vi的最短路径的长度。其初态为：若从V到Vi有弧，则D(i)为弧上权，否则为无穷大；显然，长度为D(j)=Min{D(i)|Vi∈V}的路径是从V出发的一条最短路径，此路径为(V, Vj)。下一条次短的路径可通过下面的算法求得：设次短路径的终点是Vk，则这条路径或者是(V, Vk)，或者是(V, Vj, Vk)。其长度或者是从V到Vk的弧上的权值，或者是D(j)和从Vj到Vk的弧上的权值之和。
|
|
|
|
Dijkstra算法的时间复杂度为O(n2)。但对于n个顶点的图，求每一对顶点间的最短路径，若按Dijkstra算法，求每一个顶点到其他各顶点间的最短路径，即在上面的基础上，再加一层循环，时间复杂度是O(n3)。而Floyd算法，虽然时间复杂度也是O(n3)，但形式上简单。
|
|
|
|
Floyd算法的思想是：设求顶点Vi到Vj间的最短路径，若Vi到Vj有弧，则弧上的权值是一条路径，但未必是最短路径，要经过n-1次测试。首先将顶点V1加入，即看(Vi, V1)，(V1, Vj)是否有路径，且比(Vi, Vj)低，如果是，则用后两段路径代替，并称这是Vi到Vj中间顶点序号不大于1的最短路径。再将顶点V2加入，得到Vi到Vj中间顶点序号不大于2的最短路径。如此下去，直到Vn加入，得到Vi到Vj中间顶点序号不大于n的最短路径，算法结束。
|
|
|
|
|
|
在有向图中，顶点表示事件，有向边表示活动，边上的权表示活动的持续时间，此有向图G称为边表示活动的网络，简称为AOE网（Activity On Edge）。其中，每个事件表示在它之前的活动已经完成，在它之后的事件可以开始。整个工程的开始点（入度为0）称为源点，一个完成点（出度为0）称为汇点。
|
|
|
|
关键路径是从源点到汇点之间路径长度最长的路径，它是完成工程的最短时间。路径长度是指路径上各活动的持续时间之和。
|
|
|
|
最早发生时间表示从源点V1到Vi的最长路径长度。最迟开始时间是指在不推迟整个工程完成的前提下，活动ai必须最迟开始进行的时间l(i)，活动ai必须最早开始进行的时间为e(i)。l(i)-e(i)为完成活动ai的时间余量，将l(i)=e(i)的活动叫作关键活动。
|
|
|
|
|
|
（1）从Ve(j)=0开始向前递推：Ve(j)=Max{Ve(i)+dut()},∈T, j=1,2,…,n, T是以j为头的弧的集合。
|
|
|
|
（2）从V1(n)=Ve(n)起向后递推：V1(i)=Min{V1(j)-dut()},∈S, i=n-1, …, 1, S是以i为尾的弧的集合。
|
|
|
|
|
|
（1）输入e条弧，并建立AOE网的十字链表存储结构。
|
|
|
|
（2）从源点出发，令Ve[0]=0，按拓扑排序求每个顶点的最早发生时间Ve(i)(1≤i≤n)。若拓扑排序的循环次数小于n，则说明网中存在回路，不能求关键路径。
|
|
|
|
（3）从汇点Vn出发，令V1[n-1]=Ve[n-1]，按逆拓扑排序求每个顶点的最迟发生时间V1(i)(2≤i≤n-2)。
|
|
|
|
（4）根据各顶点的Ve和V1值，校正每条弧S的最大开始时间e(s)和最迟开始时间l(s)；若e(s)=1(s)，则该弧为关键活动，输出。
|
|
|
