devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构（十一）----图的应用

作者：小小林熬夜学编程 | 2024-05-20 07:25:29

赞

踩

数据结构（十一）----图的应用

目录

一.最小生成树

1.Prim算法（普里姆）

2.Kruskal算法(克鲁斯卡尔):

二.最短路径（BFS算法）

1.单源最短路径

（1）BFS算法（无权图）

（2）Dijkstra算法（带权图，无权图）

2.各顶点间的最短路径

（1）Floyd（带权图，无权图）

三.有向无环图（DAG）

1.算术表达式

2.拓扑排序

•逆拓扑排序

3.关键路径

一.最小生成树

连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为n，则它的生成树含有n-1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。

一个带权的连通图，可能有多棵生成树（当图存在权值相同的多条边时），在所有生成树中，所有边权值之和最小的生成树就是最小生成树。

•最小生成树可能有多个，但边的权值之和总是唯一且最小的。

•最小生成树的边数 =顶点数 -1。砍掉一条则不连通，增加一条边则会出现回路。

•如果一个连通图本身就是一棵树，则其最小生成树就是它本身。

•只有连通图才有生成树，非连通图只有生成森林。

所以在最小生成树中研究的对象是带权的连通的无向图。

注意：

1.最小生成树中所有边的权值之和最小，但不能保证任意两个顶点之间的路径是最短路径。如下图所示，最小生成树中A到C的路径长度为5，但原图中C到D的最短路径长度为4。

2.最小生成树中的n-1条边不能保证是图中权值最小的n-1条边，因为权值最小的n-1条边并不一定能使图连通。例如下图，右图是左图的最小生成树，权值为3的边不再其最小生成树中。

1.Prim算法（普里姆）

从某一个顶点开始构建生成树；每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。

具体过程如下：

从P出发，代价最小的新顶点为学校，那么把学校纳入生成树。

继续将最小的新顶点纳入生成树，这里有两个代价为4的路径，都可以选择。

依次类推，直到将所有顶点纳入生成树中。根据路径不同，生成树也不同，但是最小代价一定是一样的。

时间复杂度为O(|V|^2)

从代码的角度看：

需要两个数组，一个数组记录该结点是否在生成树中，一个数组记录该结点到树的代价，如果没有与树直连，那么代价为∞。如下图，v0为初始结点，其他结点都不在生成树中：

并且其他结点到v0的代价为：

1.循环遍历所有结点，找到lowCast最低的，且还没加入树的顶点（3号顶点），将其加入生成树中。

2.再次循环遍历，更新还没加入的各个顶点的lowCast值。由于3号结点的加入，其他结点到生成树的代价更新为：

依次类推，从v0开始，每一轮都会选择新的顶点，将其放到生成树中，n个顶点就需要n-1轮处理，而每一轮的处理又需要两次循环遍历，即遍历所有的结点，并且处理他们的lowcost（到生成树的代价），所以每一轮的处理时间复杂度为O(2n)，经过n-1轮处理，那么时间复杂度为O(n^2)，即O(v^2)。

  1. //用邻接矩阵存储图
  2. #define INFINITY INT_MAX    //最大值∞
  3. #define MAX_VERTEX_NUM 20    //最大顶点个数
  4. typedef enum{DG,DN,UDG,UDN} GraphKind;    //{有向图，有向网，无向图，无向网}
  5. typedef struct ArcCell{
  6.     VRType adj;    //权值
  7.     InfoType *info;    //该弧相关信息的指针
  8. }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
  9.  
  10. typedef struct{
  11.     VertexType vexs[MAX_VERTEX_NUM];    //顶点向量
  12.     AdjMatrix arcs;    //邻接矩阵
  13.     int vexnum,arcnum;    //顶点数和弧数
  14.     GraphKind kind;    //图的种类
  15. }MGraph;
  16. bool isJoin[MAX_VERTEX_NUM]; // 记录顶点是否已加入最小生成树
  17.  
  18. int Locate(MGraph G,VertexType u){
  19.     int k=-1;
  20.     for(int i=0;i<G.vexnum;i++){
  21.         if(G.vexs[i]==u){
  22.             return i;
  23.         }
  24.     }
  25.     return k;
  26. }
  27.  
  28. void MiniSpanTree_PRIM(MGraph G,VertexType u){
  29.     //从第u个顶点出发，构造网G的最小生成树T，输出T的各条边
  30.     //记录从顶点集U到V-U的代价最小的边的辅助数组
  31.     memset(isJoin, false, sizeof(isJoin));    //初始化isJoin数组
  32.     struct{
  33.         VerTexType adjvex;
  34.         VRType lowcost;
  35.     }closedge[MAX_VERTEX_NUM];
  36.     k=Locate(G,u);
  37.     
  38.     for (j=0;j<G.vexnum;++j)
  39.         if(j!=k)    closedge[j]={u,G.arc[k][j].adj};
  40.     closedge[k].lowcost=0;
  41.     for(i=1;i<G.vexnum;i++){
  42.         k=minimum(closedge);    //求出T的下一个结点：第k顶点
  43.         printf("%d %d\n", closedge[k].adjvex, G.vexs[k]);
  44.         isJoin[k]=true;    //标记为已被访问
  45.         closedge[k].lowcost=0;
  46.         for(j=0;j<G.vexnum;++j)
  47.             if(!isJoin[j] && G.arc[k][j].adj<closedge[j].lowcost)    
  48.             //将新结点并入U后重新选择最小边
  49.                 close[j]={G.vexs[k],G.arcs[k][j].adj};
  50.     }
  51.  
  52. }
2.Kruskal算法(克鲁斯卡尔):

每次选择一条权值最小的边，使这条边的两头连通(原本已经连通的就不选)，直到所有结点都连通

具体过程如下:

P到学校权值最小，并且他们之前并没有连通，所以将两点连通。

从剩下的边中挑选权值最小的边，如图为2，由于渔村和矿场之前没有连通，所以将这两点连通。

依次类推，执行完这一步时，最小代价的边是4，但由于这条边的两头已经连通了，所以不选这条边。

依次在剩余的边当中，权值最小，且还没有连通的两点为农场和P城。

到此为止，所有的结点都连通了，这棵最小代价树最小代价也是15。

时间复杂度为O(|E|log_{2}|E|)

从代码角度看：

1.初始时，将各条边按权值排序。

2.接着，从上至下检查每条边的两个顶点是否连通（是否属于同一集合），若不连通，那么将两个点相连。

3.如上图的例子所示，下一条是v3和v5，但由于两个顶点已经属于同一个集合，所以跳过这条边，依次类推。

图中有E条边，那么总共需要进行E轮处理，在每一轮处理中，需要通过并查集判断两个顶点是否属于同一个集合，时间复杂度为O(log_{2}E),那么E轮处理，总的时间复杂度为O(|E|log_{2}|E|)。

总结：

1.Prim算法每次是选择一个顶点，Kruskal算法每次是选择一条边。

2.Prim算法的时间复杂度只和顶点的个数有关，时间复杂度为O(|V|^2)，Kruskal算法的时间复杂度只和边有关，时间复杂度为O(|E|log_{2}|E|)。所以Prim算法适用于边稠密图，也就是|E|（边）比较大的场景，Kruskal算法适用于边稀疏图，也就是|E|（边）比较小的场景。

3.因为无向连通图的最小生成树不一定唯一，所以用不同算法生成的最小生成树可能不同，但当无向连通图的最小生成树唯一时，不同算法生成的最小生成树必定是相同的。因为最小生成树算法都是基于贪心策略的，每次总是选择权值最小且满足条件的边，若各边权值不同，则每次选择的新顶点也是唯一的，所以生成的最小生成树唯一。

二.最短路径（BFS算法）

看下面的例子， “G港”是个物流集散中心，经常需要往各个城市运东西怎么运送距离最近?这就是单源最短路径问题。各个城市之间也需要互相往来，相互之间怎么走距离最近?这就是每对顶点间的最短路径。

注：最短路径一定是简单路径，即路径上的各顶点均不互相重复。

1.单源最短路径
（1）BFS算法（无权图）

无权图可以视为一种特殊的带权图，只是每条边的权值都为1。

在BFS算法中，1号顶点，6号顶点与2号顶点的距离为1

5，3，7与2的距离为2

4，8与2的距离为3

求2号顶点到其他顶点的最短路径：

  1. #define INFINITY INT_MAX    //最大值∞
  2.  
  3. void BFS_MIN_Distance(Graph G,int u){
  4.     //d[i]表示从u到i结点的最短路径
  5.     for(i=0;i<G.vexnum;i++){
  6.         d[i] = INT_MAX;    //初始化路径长度
  7.         path[i]=-1;    //最短路径从哪个顶点过来
  8.     }
  9.     d[u] =0;
  10.     visited[u]=TRUE;
  11.     EnQueue(Q,u);
  12.     while(!isEmpty(Q)){
  13.         DeQueue(Q,u);
  14.         for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w)){
  15.             if(!visited[w]){
  16.                 d[w]=d[u]+1;    //路径长度+1
  17.                 path[w]=u;    //最短路径应从u到w
  18.                 visited[w]=TRUE;    //设为以访问标记
  19.                 EnQueue(Q,w);    //顶点w入队
  20.             }//if
  21.         }//for
  22.     }//while
  23. }

具体过程如下：
从2号顶点出发，则将2号顶点出队，并且将2号顶点邻接的点的路径长度设为1(d[w]=d[u]+1)，也就是将d[1],d[6]=1，并且将path[1],path[6]=2，表示最短路径从2过来

 

其余依次类推：

通过path数组可知，2到8的最短路径为：8<--7<--6<--2

（2）Dijkstra算法（带权图，无权图）

BFS算法只能用于无权图，对于带权图则不再适用。例如下图，若要求G港到R城的最短路径，用BFS算法得到的最短路径是10，其实从P城再到R城才是最短路径7。

Dijkstra算法就能解决这个问题，首先需要初始化三个数组：

接着循环遍历所有结点，找到还没确定最短路径，且dist 最小的顶点Vi(final=false,dis[i]最小)，令final[i]=ture。在v1，v2，v3，v4四个顶点中，最小的值是5。

检查所有与v4相邻的顶点，若其final值为false，则更新dist和path的信息。由于v0到v4的路径是5，v4到v1的距离为3，所以找到了从v0到v1的更短的路径，即5+3=8。

现在final=false的顶点当中，路径最小的是7，所以现在处理v3，将final[3]=true。检查可以从v3过去的顶点，若其final=false，则更新dist和path的信息。

继续以上步骤，最后得到：

v0到v2的最短（带权）路径长度为dist[2]=9

通过path[]可知，v0到v2的最短路径：v2<--v1<--v4<--v0

时间复杂度为O(n^2)即O(|V|^2)，因为从final=false的顶点中找到dist最小的顶点，并将其设为final[i]=false，时间复杂度为O(n)。并且需要更新与该点相邻的final=false的点的信息，若图为邻接矩阵存储，要找到与他相邻的所有的点，就是要扫描该点对应的行，时间复杂度为O(n),所以每一轮处理需要的时间复杂度为O(n)+O(n)=2O(n)，总共需要n-1轮处理，所以算法的时间复杂度为O(|V|^2)。

Dijkstra算法和Prim算法的区别： 

Prim算法适用于带权的连通的无向图，而Dijkstra算法不仅可用于带权连通的无向图，也可用于带权连通的有向图。Prim算法数组记录的是顶点加入到目前生成树的最小代价，dist数组记录的是当前顶点到指定顶点的最短路径的值。

若带权图中有负权值的边，那用Dijkstra算法找到的路径可能不是最短路径，所以Dijkstra算法不适用于有负权值的带权图。但是Floyd算法可以用于负权图。

  1. void DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D){
  2.     //求有向网G的v0顶点到其余顶点v的最短路径P[v]及其带权长度D[v]
  3.     //若P[v][w]为TRUE，则w为从v0到v当前求得最短路径的顶点
  4.     for(v=0;v<G.vexnum;++v){
  5.         final[v]=FALSE;    D[v]=G.arcs[v0][v];
  6.         for(w=0;w<G.vexnum;++w)    p[v][w]=FALSE;    //设空路径
  7.         if(D[v]<INFINITY){
  8.             P[v][v0]=TRUE;
  9.             p[v][v]=TRUE;
  10.         }
  11.     }
  12.     D[v0]=0;    final[v0]=TRUE;    //初始化，v0顶点属于S集
  13.     //开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集中 
  14.     for(i=1;i<G.vexnum;++i){
  15.         min=INFINITY;    //当前所知离v0顶点的最近距离
  16.         for(w=0;w<G.vexnum;++w)
  17.             if(!final[w]){
  18.                 if(D[w]<min){v=w;min=D[w];}    //w顶点离顶点更近
  19.         final[v]=TRUE;
  20.         for(w=0;w<G.vexnum;++w)
  21.             if(!final[w] && (min+G.arcs[v][w])<D[w])){
  22.                 D[w]=min+G.arcs[v][w];
  23.                 P[w]=P[v];    P[w][w]=TRUE;    //P[w]=P[v]+P[w]
  24.             }
  25.     }
  26. }
2.各顶点间的最短路径
（1）Floyd（带权图，无权图）

从v2到v1的路径为∞，表示从v2到v1没有路径可走：

1.若允许从v0中转，则v2到v1的路径可变为v2-->v0-->v1，距离为11：

也就是：

广义化则变为：

更新A和path后，矩阵为：

2.若允许在v0，v1中转，在更新的矩阵的基础上，扫描所有的元素，只有A[0][2]满足条件：

更新后的矩阵如下：

3.若允许在v0，v1，v2中转，在更新的矩阵的基础上，扫描所有元素，只有A[1][0]满足条件

更新后的矩阵如下：

所以从A^{(-1)}和path^{(-1)}开始，经过n轮递推，得到A^{(n-1)}和path^{(n-1)}

  1. void FLOYD(MGraph G,PathMatrix &P[],DistanceMatrix &D){
  2.     //P[v][w]表示最短路径，D[v][w]表示带权路径长度
  3.     //若P[v][w][u]为TRUE,则u是从v到w当前求得的最短路径
  4.     for(v=0;v<G.vexnum;++v)
  5.         for(w=0;w<G.vexnum;++w){
  6.             D[v][w]=G.arcs[v][w];
  7.             for(u=0;u<G.vexnum;++u)    P[v][w][u]=FALSE;
  8.                 if(D[v][w]<INFINITY){
  9.                     P[v][w][u]=TRUE;p[v][w][w]=TRUE; 
  10.                 }
  11.         }
  12.     for(u=0;u<G.vexnum;++u)
  13.         for(v=0;v<G.vexnum;++v)
  14.             for(w=0;w<G.vexnum;++w)
  15.                 if(D[v][u]+D[u][w]<D[v][w]){
  16.                     D[v][w]=D[v][u]+D[u][w];
  17.                     for(i=0;i<G.vexnum;++i)
  18.                         P[v][w][i]=P[v][u][i] || P[u][w][i];    //更新最短路径
  19.                 }
  20. }

 由上面的代码可得，时间复杂度为O(n^3)即O(|V|^3)。

再考虑更加复杂的例子：

前面的步骤相同，直接考虑以v2作为中转：

可以更新的最短路径如下：

注意：A[0][3]的路径可以转化为A[0][2]+A[2][3]，其实A[2][3]之间是没有直接路径的，但是在v2进行中转 是在v0，v1也允许中转 的基础上进行的，之前已经更新了从v2到v3的路径,即：

v2->v1->v3

所以A[0][2]+A[2][3]实际经过的路径是v0->v2->v1->v3

以此类推，最终得到：

如何通过矩阵找完成的路径，例如，找v0到v4的最短路径，p[0][4]=3，v0->v3->v4:

由于p[0][4]不为-1，所以中间还有其他顶点。

依次看v0->v3和v3->v4，由于v0->v3的path[0][3]=2，说明中间还经过了其他结点:

v0->v2->v3。

p[3][4]=-1，说明中间没有经过任何顶点。

继续拆解v0->v2->v3，v0->v2的path[0][2]=-1，中间不经过其他顶点，v2->v3的path[2][3]=1，说明中间还经过了其他顶点，v2->v1->v3

继续拆解v2->v1->v3，v2->v1的path[2][1]=-1，中间不经过其他顶点，v1->v3的path[1][3]=-1，中间不经过任何顶点，至此拆解完毕，最后得到从v0到v4的完整路径为：
v0->v2->v1->v3->v4

Floyd算法可以用于负权图，例子如下：

但是Floyd 算法不能解决带有“负权回路”的图(有负权值的边组成回路)，这种图有可能没有最短路径。例如下图，可以观察到，如果回路走的次数越多，那么其带权路径会越来越小。

总结：

其实也可用 Dijkstra 算法求所有顶点间的最短路径，重复|V|次即可（也就是分别以图的各个顶点作为源顶点，求源顶点到达其他结点的最短路径），总的时间复杂度也是O(|V|^3)

三.有向无环图（DAG）

1.算术表达式

若一个有向图中不存在环，则称为有向无环图，简称DAG图(Directed Acyclic Graph)，常用作描述表达式。

之前我们用树表示算术表达式，对于下面的式子所画的树，红绿两个子树是相同的。

我们可以丢弃重复的部分，节省存储空间，如下图所示，这个图就是一个有向无环图：

如何完全丢弃重复的部分呢？

1.把各个操作数不重复地排成一排

2.标出各个运算符的生效顺序

3.按生效顺序加入运算符：

第1，2个生效的是两个"+"号：

第3个生效的是*号，需要用到+号产生的运算结果，所以比+号更上一层：

依次类推：

，

4.由于各个操作数是不重复，只需要检查操作符即可。所以自底向上逐层检查同层的运算符是否可以合并。

在第一层中，第一个“+”左右是a，b  右边三个"+"左边都是c，d，所以可以合并。

依次类推，得到最简的算数表达式如下：

注：为什么只检查同层呢，拿第一层为例，第一层的操作符左右两边肯定是操作数，而第二层的操作符，左右两边肯定有复合的操作数，所以第一层操作数和第二层操作数是不可能合并的。

再举一个例子：

若改变操作符的生效顺序，那么有向无环图的形态是不唯一的。

2.拓扑排序

AOV网（Activity On Vertex NetWork,用顶点表示活动的网）。用DAG图(有向无环图)表示一个工程。顶点表示活动，有向边<V_{i}，V_{j}>表示活动V_{i}必须先于活动V_{j}进行。

拓扑排序的实现如下：

① 从AOV网中选择一个没有前驱(入度为0)的顶点并输出。
② 从网中删除该顶点和所有以它为起点的有向边。
③ 重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。

上面是基于BFS算法的拓扑排序，当然也可以基于DFS算法，这里只讲使用BFS算法的拓扑排序。

每个AOV网可能有一个或多个拓扑排序序列：例如下图，可以先准备厨具，也可以先买菜。

若一个图中有回路，那么这个图就不能拓扑排序，例如下图，执行到某一步时会发现，当前所有顶点的入度都大于0，拓扑排序无法继续进行。

补充：

1.若一个有向图的邻接矩阵为三角矩阵（对角线以上或以下的元素为0），则该图的拓扑序列必定存在。

因为邻接矩阵中对角线以下的元素全为0，若存在< i,j >，则必有 i<j，由传递性可知，图中路径的顶点编号是依次递增的，例如A_{1,2},A_{1,3}....假设存在环k-->..-->j-->k，由题设可知k<j<k，矛盾了，所以不存在环，那么拓扑序列必定存在。例如下图：

但是这不能说明拓扑序列是唯一的，例如某有向图的邻接矩阵如下图所示，那么这个有向图存在两个拓扑序列。

2.若有向图的拓扑有序序列唯一，则图中入度为0和出度为0的顶点都仅有1个。

3.若有向图的拓扑有序序列唯一，则图中每个顶点的入度和出度最多为1。(x)

反例：

4.若有向图的拓扑有序序列唯一，并不能唯一确定该图。下面的两个有向无环图中，拓扑序列都为V1,V2,V3,V4。

拓扑排序的代码如下：

  1. #define MaxVertexNum 100    //图中顶点数目的最大值
  2. typedef struct ArcNode{    //边表结点
  3.     int adjvex;    //该弧所指向的顶点的位置
  4.     struct ArcNode *nextarc;     //指向下一条弧的指针
  5.     //InfoType info;    //网的边权值   
  6. }ArcNode;
  7.  
  8. typedef struct VNode{    //顶点表结点
  9.     VertexType data;    //顶点信息
  10.     ArcNode *firstarc;    //指向第一条依附该顶点的弧的指针
  11. }VNode,AdjList[MaxVertexNum];
  12.  
  13. typedef struct{
  14.     AdjList vertices;    //邻接表
  15.     int vexnum,arcnum;    //图的顶点数和弧数
  16. }Graph;    //Graph是以邻接表存储的图类型
  17.  
  18. bool TopologicalSort(Graph G){
  19.     InitStack(S);    //初始化栈，存储入度为0的顶点
  20.     for(int i=0;i<G.vexnum;i++)
  21.         if(indegree[i]==0)
  22.             Push(S,i);    //将所有入度为0的顶点进栈
  23.         int count=0;    //计数，记录当前已经输出的顶点数
  24.         while(!IsEmpty(S)){    //栈不空，则存在入度为0的顶点
  25.             Pop(S,i);
  26.             print[count++]=i;
  27.             for(p=G.vertices[i].firstarc;p;p->nextarc){
  28.             //将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈S
  29.                 v=p->adjvex;
  30.                 if(!(--indegree[v]))
  31.                     Push(S,v);    //入度为0，则入栈
  32.             }
  33.         }
  34.         if(count<G.vexnum)    //在上图中，count=5(结点数)，表示拓扑排序成功
  35.             return false;  //拓扑失败，有向图有回路
  36.         else
  37.             return true;    //拓扑排序成功
  38. }

若采用邻接表，由于该算法中，每一个顶点都会被处理一次，每一条边也会被遍历一次，所以时间复杂度为O(|V|+|E|)，若采用邻接矩阵，把所有的边都遍历一遍，其实就是扫描整个邻接矩阵，所以时间复杂度为O(|V|^2)。

•逆拓扑排序

逆拓扑排序和拓扑排序的步骤是一样的，只是每一次删除的是出度为0的顶点

具体过程如下：

① 从AOV网中选择一个没有后继(出度为0)的顶点并输出。

② 从网中删除该顶点和所有以它为终点的有向边。

③ 重复①和②直到当前的AOV网为空。

对于逆拓扑排序，不同的存储结构对逆拓扑排序的时间复杂度影响很大。因为删除某一个顶点，也需要删除指向这个顶点的边。若采用邻接表，要找到指向一个顶点的边，就意味着需要遍历整个表。而采用邻接矩阵，只需要遍历该点对应的列即可。

可以使用逆邻接表，邻接表中，每个结点的边表保存的是从这个结点出来的边的信息，而逆邻接表中，每个结点的边表是指向结点的边的信息。

可以用DFS算法实现逆拓扑排序：

  1. #define MAX_VERTEX_NUM 100
  2.  
  3. bool visited[MAX_VERTEX_NUM]; //是否已被访问过
  4.  
  5. void DFSTraverse(Graph G){    //对图进行深度优先遍历
  6.     for(v=0;v<G.vexnum;++v)
  7.         visited[v]=FALSE;
  8.     for(v=0;v<G.vexnum;++v)
  9.         if(!visited[v])
  10.             DFS(G,v);
  11. }
  12.  
  13. //用栈递归
  14. void DFS(Graph G,int v){    //从顶点v出发，深度优先遍历图G
  15.     int w;
  16.     visited[v]=TRUE;
  17.     for(w=FirstNeighbor(G,v);w>=0;w=Neighbor(G,v,w))
  18.         if(!visited[w]){
  19.             DFS(G,w);
  20.         }
  21.     print(v);    //各个顶点的信息在退栈时输出
  22. }
  23. //对于逆拓扑排序，各个顶点的信息在退栈时输出，那么也可以想到使用DFS实现拓扑排序的思想：
  24. 在DFS调用过程中设定一个时间标记，当DFS调用结束时，对各结点计时，进而按结束时间从大到小排序，可以得到一个拓扑序列

递归过程如下：

① 以0号顶点作为入口，调用DFS函数，并把0号顶点的visited[ ]设为true：

② 从0号顶点出发，找到第一个与其邻接的顶点，也就是1号顶点，且1号顶点此时没有被访问过，进入下一级的DFS函数：

③ 依次类推，访问到4号顶点后，与4号相邻的顶点都被访问过了，所以不用执行更深一层的DFS了，直接将4号顶点打印输出。

④ 回溯到3号顶点，3号顶点也找不到与之相邻，且没有被访问过的顶点，所以直接打印输出3号顶点。1号和0号顶点同理。所以现在打印输出了4，3，1，0

⑤递归结束：

⑥ 继续回到for循环，找到下一个没有被访问的顶点，即2号顶点：

⑦ 将2号顶点入栈，由于其没有未访问过的邻接点，所以不需要进入更深层的DFS，直接输出打印2号顶点：

得到逆拓扑排序：4，3，1，0，2  

和拓扑排序相同，拓扑排序和逆拓扑排序序列可能是不唯一的，若图中有环，则不存在拓扑排序/逆拓扑排序序列。

逆拓扑排序如何检测图中是否有环呢？

除了用visited[ ]标记已访问的元素外，可以再增加一个flag[ ]数组判断当前结点是否还在递归栈中。

① 每次递归结束后，将当前结点flag[v]=0,也就是回溯。

② 如果某次访问遇到了visited[v]=1的点，判断flag[v]是否等于1（flag[v]=1），若是的话，说明环路存在。例如下图，递归到2号结点时，2号结点访问3号结点，发现其visited[3]=1，并且flag[3]=1，说明3还在递归栈中，则说明下图存在环路。

改进代码如下:

  1. #define MAX_VERTEX_NUM 100
  2.  
  3. bool visited[MAX_VERTEX_NUM]; //是否已被访问过
  4. bool flag[MAX_VERTEX_NUM];  //是否孩子递归栈中
  5.   
  6. void DFSTraverse(Graph G){    //对图进行深度优先遍历  
  7.     for(int v=0; v<G.vexnum; ++v) {  
  8.         visited[v] = FALSE;  
  9.         flag[v] = FALSE;  
  10.     }  
  11.     for(int v=0; v<G.vexnum; ++v)  
  12.         if(!visited[v])  
  13.             DFS(G, v);  
  14. }  
  15.   
  16. void DFS(Graph G, int v){    //从顶点v出发，深度优先遍历图G  
  17.     int w;  
  18.     visited[v] = TRUE;  
  19.     flag[v] = TRUE; // 标记v在栈中  
  20.   
  21.     for(w=FirstNeighbor(G, v); w>=0; w=Neighbor(G, v, w)) {  
  22.         if(!visited[w]){  
  23.             DFS(G, w);  
  24.         } else if(flag[w]) { // 如果w已被访问且仍在栈中，则存在环路  
  25.             printf("存在环路！\n"); // 或者你可以设置一个全局变量来记录这个信息  
  26.             return; // 可以选择立即返回或继续遍历（取决于你的需求）  
  27.         }  
  28.     }  
  29.   
  30.     flag[v] = FALSE; // 在退栈时设置v不在栈中  
  31.     print(v); // 各个顶点的信息在退栈时输出  
  32. }

3.关键路径

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销(如完成活动所需的时间)，称之为用边表示活动的网络，简称AOE网(Activity On Edge NetWork)。上面说的AOV网是用顶点表示活动，而AOE网使用边表示活动，而顶点表示的是一个个事件。

注：AOV网和AOE网都是在有向无环图的基础上进行的。

AOE网有以下两个性质：

① 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；

② 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。另外，有些活动是可以并行进行的（例如上图，洗番茄和打鸡蛋是可以同时进行的，而洗番茄和切番茄不能同时进行）。

AOE网的相关概念：

① 在AOE网中仅有一个入度为0的顶点，称为开始顶点(源点)，它表示整个工程的开始;也仅有一个出度为0的顶点，称为结束顶点(汇点)，它表示整个工程的结束。

② 从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。
完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长。

③ 

事件v_{k}的最早发生时间ve(k)--决定了所有从vk开始的活动能够开工的最早时间。

活动a_{i}的最早开始时间e(i)--指该活动弧的起点所表示的事件的最早发生时间。

④ 

事件v_{k}的最迟发生时间vl(k)--它是指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间。

活动a_{i}的最迟开始时间--它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。例如下图，切番茄这一活动必须在4 - 3=1这个时刻开始，否则会推迟整个工程完成的进度。

⑤将活动最早开始时间和活动最晚开始时间结合起来看：

活动a_{i}的最早开始时间e(i)--指该活动弧的起点所表示的事件的最早发生时间。

活动a_{i}的最迟开始时间--它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。

观察上图可以发现，只有打鸡蛋这个活动可以拖到2时刻开始，其余活动是不能拖延的。

活动a_{i}的时间余量d[i]=l[i]-e[i]，表示在不增加完成整个工程所需总时间的情况下，活动a_{i}可以拖延的时间。

活动的时间余量为零，则说明该活动必须要如期完成，d(i)=0即l(i)=e(i)的活动a_{i}是关键活动。由关键活动组成的路径就是关键路径。

（1）求所有事件的最早发生时间ve()

源点的最早发生时间是0，其余顶点的最早发生时间是前驱顶点的最早发生时间+活动消耗的时间

ve(源点)=0

ve(k)=Max{ve(j)+Weight(v_{j}+v_{k})}，vj为vk的任意前驱。

例如下图，v3的最早发生时间是2，v4有两个直接前驱。若从v2过来，那么v4最早发生时间是3+2=5。若从v3过来，v4的最早发生时间为2+4=6。只有所有指向该顶点的活动都结束后，这个时间才能发生，所以取更大的值，v4的最早发生时间是6。

依次类推得到所有事件的最早发生时间：

（2）求所有时间的最迟发生时间vl()

按逆拓扑排序序列，依次求各个顶点的vl(k)：

vl(6)=ve(6)=8        //终点所允许的最迟发生时间和其最早发生时间是一样的。

vl(k)=Min{vl(j)-Weight(v_{k},v_{j})}，v_{j}为v_{k}的任意后继，例如下图，v5的最迟发生时间等于：

v6(后继)的最迟发生时间-1=7

如下图，v2有两个直接后继，若以v5为后继活动，v2的最迟发生时间7-3=4。若以v4为后继活动，v4的最迟发生时间是6-2=4。取最小值，所以v2的最迟发生时间是4。

依次类推： 

（3）求所有活动的最早发生时间e()

若边<v_{k},v_{j}>表示活动a_{i}，则有e(i)=ve(k)，也就是 每个活动的最早发生时间就是这个活动的弧尾所连的事件的最早发生时间。

得到所有活动的最早发生时间如下：

（4）求所有活动的最迟发生时间l()

若边<v_{k},v_{j}>表示活动a_{i}，则有l(i)=vl(j)-Weight(v_{k},v_{j})，也就是 这条弧所指向的事件的最晚发生时间 - 这条弧的权值 或者 也可以通过这条弧的弧尾所连事件的最晚发生时间确定活动的最迟发生时间。例如下图，活动a4的最迟发生时间就是7-3=4 或者 v2事件的最晚发生事件也是4。

依次类推，所有活动的最迟发生时间：

（5）求时间余量 d(i)=l(i)-e(i)

只需要用活动的最晚发生时间-活动的最早发生时间。

a2，a5，a7活动的时间余量都为0，所以这几个活动是关键活动，这几个活动对应的边就是关键路径。

关键活动、关键路径的特性：

•若关键活动耗时增加，则整个工程的工期将增长
•缩短关键活动的时间，可以缩短整个工程的工期

•当缩短到一定程度时，关键活动可能会变成非关键活动

例如下图，切番茄是关键活动，若将切番茄的时间缩短为1，那么整个工程的工期缩短，也就是4，但是若继续压缩切番茄的时间，那么他就不是关键活动了，因为他没办法让工程缩短，打鸡蛋和炒菜的时间最少需要4。关键活动变为打鸡蛋和炒菜。

所以不是关键路径上的活动越压缩，整个工程的工期就会越提前。

•可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

如上图所示，v1->v2->v3->v4是一条关键路径，v1->v3->v4是一条关键路径。加快包含在所有关键路径上的关键活动，例如炒菜，才能缩短工期。

例题：

下列 AOE 网表示一项包含8个活动的工程。通过同时加快若干活动的进度可缩短整个工程的工期。在下列选项中，加快其进度就可缩短工程工期的是（C）

A.c和f        B.d和c        C.f和d        D.f和h

只有当所有关键路径的活动时间同时减少时，才能缩短工期。即正确的选项必须能涵盖所有的关键路径。

来做几道判断题：

1.改变网上某一关键路径上的任意一个关键活动后，必将产生不同的关键路径。（x）

这里如果说改变网上所有关键路径上的公共活动，也不一定会产生不同的关键路径。因为如果是延长这一公共活动，则必然不会产生不同的关键路径，只有缩短才可能。

2.在AOE图中，关键路径上的活动时间延长多少，整个工期就会随之延长多少。（√）

3.缩短所有关键路径上共有的任意一个关键活动的持续时间才可以缩短关键路径的长度（√）

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/596695
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号