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

一.最小生成树

1.Prim算法（普里姆）

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

二.最短路径（BFS算法）

1.单源最短路径

（1）BFS算法（无权图）

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

2.各顶点间的最短路径

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

三.有向无环图（DAG）

1.算术表达式

2.拓扑排序

•逆拓扑排序

3.关键路径

一.最小生成树

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

一个带权的连通图，可能有多棵生成树，在所有生成树中，所有边权值之和最小的生成树就是最小生成树。

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

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

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

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

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

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)。

//用邻接矩阵存储图
#define INFINITY INT_MAX    //最大值∞
#define MAX_VERTEX_NUM 20    //最大顶点个数
typedef enum{DG,DN,UDG,UDN} GraphKind;    //{有向图，有向网，无向图，无向网}
typedef struct ArcCell{
    VRType adj;    //权值
    InfoType *info;    //该弧相关信息的指针
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct{
    VertexType vexs[MAX_VERTEX_NUM];    //顶点向量
    AdjMatrix arcs;    //邻接矩阵
    int vexnum,arcnum;    //顶点数和弧数
    GraphKind kind;    //图的种类
}MGraph;
bool isJoin[MAX_VERTEX_NUM]; // 记录顶点是否已加入最小生成树

int Locate(MGraph G,VertexType u){
    int k=-1;
    for(int i=0;i<G.vexnum;i++){
        if(G.vexs[i]==u){
            return i;
        }
    }
    return k;
}

void MiniSpanTree_PRIM(MGraph G,VertexType u){
    //从第u个顶点出发，构造网G的最小生成树T，输出T的各条边
    //记录从顶点集U到V-U的代价最小的边的辅助数组
    memset(isJoin, false, sizeof(isJoin));    //初始化isJoin数组
    struct{
        VerTexType adjvex;
        VRType lowcost;
    }closedge[MAX_VERTEX_NUM];
    k=Locate(G,u);
    
    for (j=0;j<G.vexnum;++j)
        if(j!=k)    closedge[j]={u,G.arc[k][j].adj};
    closedge[k].lowcost=0;
    for(i=1;i<G.vexnum;i++){
        k=minimum(closedge);    //求出T的下一个结点：第k顶点
        printf("%d %d\n", closedge[k].adjvex, G.vexs[k]);
        isJoin[k]=true;    //标记为已被访问
        closedge[k].lowcost=0;
        for(j=0;j<G.vexnum;++j)
            if(!isJoin[j] && G.arc[k][j].adj<closedge[j].lowcost)    
            //将新结点并入U后重新选择最小边
                close[j]={G.vexs[k],G.arcs[k][j].adj};
    }

}

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|（边）比较小的场景。

二.最短路径（BFS算法）

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

1.单源最短路径

（1）BFS算法（无权图）

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

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

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

4，8与2的距离为3

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

#define INFINITY INT_MAX    //最大值∞

void BFS_MIN_Distance(Graph G,int u){
    //d[i]表示从u到i结点的最短路径
    for(i=0;i<G.vexnum;i++){
        d[i] = INT_MAX;    //初始化路径长度
        path[i]=-1;    //最短路径从哪个顶点过来
    }
    d[u] =0;
    visited[u]=TRUE;
    EnQueue(Q,u);
    while(!isEmpty(Q)){
        DeQueue(Q,u);
        for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w)){
            if(!visited[w]){
                d[w]=d[u]+1;    //路径长度+1
                path[w]=u;    //最短路径应从u到w
                visited[w]=TRUE;    //设为以访问标记
                EnQueue(Q,w);    //顶点w入队
            }//if
        }//for
    }//while
}

具体过程如下：
从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算法数组记录的是顶点加入到目前生成树的最小代价，dist数组记录的是当前顶点到指定顶点的最短路径的值。

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

void DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D){
    //求有向网G的v0顶点到其余顶点v的最短路径P[v]及其带权长度D[v]
    //若P[v][w]为TRUE，则w为从v0到v当前求得最短路径的顶点
    for(v=0;v<G.vexnum;++v){
        final[v]=FALSE;    D[v]=G.arcs[v0][v];
        for(w=0;w<G.vexnum;++w)    p[v][w]=FALSE;    //设空路径
        if(D[v]<INFINITY){
            P[v][v0]=TRUE;
            p[v][v]=TRUE;
        }
    }
    D[v0]=0;    final[v0]=TRUE;    //初始化，v0顶点属于S集
    //开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集中 
    for(i=1;i<G.vexnum;++i){
        min=INFINITY;    //当前所知离v0顶点的最近距离
        for(w=0;w<G.vexnum;++w)
            if(!final[w]){
                if(D[w]<min){v=w;min=D[w];}    //w顶点离顶点更近
        final[v]=TRUE;
        for(w=0;w<G.vexnum;++w)
            if(!final[w] && (min+G.arcs[v][w])<D[w])){
                D[w]=min+G.arcs[v][w];
                P[w]=P[v];    P[w][w]=TRUE;    //P[w]=P[v]+P[w]
            }
    }
}

2.各顶点间的最短路径

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

从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)}$

void FLOYD(MGraph G,PathMatrix &P[],DistanceMatrix &D){
    //P[v][w]表示最短路径，D[v][w]表示带权路径长度
    //若P[v][w][u]为TRUE,则u是从v到w当前求得的最短路径
    for(v=0;v<G.vexnum;++v)
        for(w=0;w<G.vexnum;++w){
            D[v][w]=G.arcs[v][w];
            for(u=0;u<G.vexnum;++u)    P[v][w][u]=FALSE;
                if(D[v][w]<INFINITY){
                    P[v][w][u]=TRUE;p[v][w][w]=TRUE; 
                }
        }
    for(u=0;u<G.vexnum;++u)
        for(v=0;v<G.vexnum;++v)
            for(w=0;w<G.vexnum;++w)
                if(D[v][u]+D[u][w]<D[v][w]){
                    D[v][w]=D[v][u]+D[u][w];
                    for(i=0;i<G.vexnum;++i)
                        P[v][w][i]=P[v][u][i] || P[u][w][i];    //更新最短路径
                }
}

由上面的代码可得，时间复杂度为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网为空或当前网中不存在无前驱的顶点为止。

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

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

拓扑排序的代码如下：

#define MaxVertexNum 100    //图中顶点数目的最大值
typedef struct ArcNode{    //边表结点
    int adjvex;    //该弧所指向的顶点的位置
    struct ArcNode *nextarc;     //指向下一条弧的指针
    //InfoType info;    //网的边权值   
}ArcNode;

typedef struct VNode{    //顶点表结点
    VertexType data;    //顶点信息
    ArcNode *firstarc;    //指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];

typedef struct{
    AdjList vertices;    //邻接表
    int vexnum,arcnum;    //图的顶点数和弧数
}Graph;    //Graph是以邻接表存储的图类型

bool TopologicalSort(Graph G){
    InitStack(S);    //初始化栈，存储入度为0的顶点
    for(int i=0;i<G.vexnum;i++)
        if(indegree[i]==0)
            Push(S,i);    //将所有入度为0的顶点进栈
        int count=0;    //计数，记录当前已经输出的顶点数
        while(!IsEmpty(S)){    //栈不空，则存在入度为0的顶点
            Pop(S,i);
            print[count++]=i;
            for(p=G.vertices[i].firstarc;p;p->nextarc){
            //将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈S
                v=p->adjvex;
                if(!(--indegree[v]))
                    Push(S,v);    //入度为0，则入栈
            }
        }
        if(count<G.vexnum)    //在上图中，count=5(结点数)，表示拓扑排序成功
            return false;  //拓扑失败，有向图有回路
        else
            return true;    //拓扑排序成功
}

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

•逆拓扑排序

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

具体过程如下：

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

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

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

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

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

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

void DFSTraverse(Graph G){    //对图进行深度优先遍历
    for(v=0;v<G.vexnum;++v)
        visited[v]=FALSE;
    for(v=0;v<G.vexnum;++v)
        if(!visited[v])
            DFS(G,v);
}

//用栈递归
void DFS(Graph G,int v){    //从顶点v出发，深度优先遍历图G
    int w;
    visited[v]=TRUE;
    for(w=FirstNeighbor(G,v);w>=0;w=Neighbor(G,v,w))
        if(!visited[w]){
            DFS(G,w);
        }
    print(v);    //各个顶点的信息在退栈时输出
}

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

如何检测图中是否有环呢？可以增加一个一个数组path[ ]来记录从起点到当前节点的路径。如果发现下一个节点已经被访问过，并且不是当前节点的上一个节点，那么就说明存在回路。

改进代码如下:

#define MAX_VERTEX_NUM 100  // 定义最大顶点数

int visited[MAX_VERTEX_NUM];  // 访问标志数组
int path[MAX_VERTEX_NUM];     
// 路径数组，用来记录上一个访问的结点，例如path[1]=0表示结点1的上一个结点是0

void DFSTraverse(Graph G){    //对图进行深度优先遍历
    for(v=0;v<G.vexnum;++v){
        visited[v]=FALSE;
        path[v]=-1;    //初始化路径数组
    }
    for(v=0;v<G.vexnum;++v)
        if(!visited[v])
            DFS(G,v);
}

//用栈递归
void DFS(Graph G,int v){    //从顶点v出发，深度优先遍历图G
    int w;
    visited[v]=TRUE;
    for(w=FirstNeighbor(G,v);w>=0;w=Neighbor(G,v,w)){
        if(!visited[w]){    //有未被访问过的邻接点
            path[w]=v;
            DFS(G,w);        
        }else if(path[v]!=w){    
        //下一个结点已经被访问过，并且不是当前访问的结点的上一个结点，则存在环路
            return;    
        }    
    }
    print(v);
}

3.关键路径

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销(如完成活动所需的时间)，称之为用边表示活动的网络，简称AOE网(Activity On Edge NetWork)。上面说的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

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

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

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

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

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

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

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

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

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

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

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