现在位置: 首页 / 数据结构 / 正文

图-数据结构

图-数据结构

基本概念：
图的定义

图G（Graph）由顶点集V（Vertex）和边集E（Edge）组成，记为G=(V，E)，其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系（边）集合。若V={v~1~，v~2~，...，v~n~}，则用|V|表示图G中顶点的个数，也称图G的阶，E={（u，v）| u∈V，v∈V}，用|E|表示图G中边的条数。

注意：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集

图的应用场景非常广泛，涵盖了计算机科学、人工智能、社交网络、交通系统、生物信息学等多个领域。

无向图、有向图

若E是无向边（简称边）的有限集合时，则图G为无向图。边是顶点的无序对，记为（v，w）或（w，v），因为（v，w）=（w，v），其中v，w是顶点。可以说顶点w和顶点v互为邻接点。边（v，w）依附于顶点w和v，或者说边（v，w）和顶点v，w相关联。

表示方法：

G~2~ = (V~2~, E~2~)

V~2~ = {A, B, C, D, E}

E~2~ = {(A, B), (B, D), (B, E), (C, D), (C, E), (D, E)}

无向图

若E是有向边（也称弧）的有限集合时，则图G为有向图。弧是顶点的有序对，记为<v，w>，其中v，w是顶点，v称为弧尾，w称为弧头，<v，w>称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v。<v，w>≠<w，v>

表示方法：

G~1~ = (V~1~, E~1~)

V~1~ = {A, B, C, D, E}

E~1~ = {==<A, B>==, <A, C>, <A, D>, <A, E>, ==<B, A>==, <B, C>, <B, E>, <C, D>}

有向图

简单图、多重图

简单图：不存在重复边和不存在顶点到自身的边

多重图：图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则G为多重图

顶点的度、入度、出度

对于无向图：顶点v的度是指依附于该顶点的边的条数，记为TD(v)。在具有n个顶点、e条边的无向图中，$\sum\limits_{i=1}^nTD(v)=2e$，即无向图的全部顶点的度的和等于边数的2倍

对于有向图：入度是以顶点v为终点的有向边的数目，记为ID(v)；出度是以顶点v为起点的有向边的数目，记为OD(v)。顶点v的度等于其入度和出度之和，即TD(v)=ID(v)+OD(v)。

在具有n个顶点、e条边的有向图中，$\sum\limits{i=1}^nID(v)=\sum\limits{i=1}^nOD(v)=e$。图中所有顶点的入度之和等于所有顶点的出度之和（因为每条边都贡献了一个入度和一个出度，除非它是孤立边或环的一部分，但这种情况不影响总和）。

顶点-顶点的关系描述

顶点之间可能不存在路径，有向图的路径也是向的

路径：顶点v~p~到顶点v~q~之间的一条路径是指顶点序列，v~p~，v~i1~，v~i2~，...，v~im~，vq

回路：第一个顶点和最后一个顶点相同的路径称为回路或环

简单路径：在路径序列中，顶点不重复出现的路径称为简单路径

简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路

路径长度：路径上边的数目

点到点的距离：从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷

无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的

有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的

连通图、强连通图

子图、生成子图

子图是指从一个较大的图（称为原图或母图）中通过删除零个或多个边（同时可能删除一些或零个顶点，但通常不强制要求删除顶点）而得到的图。换句话说，如果图G'的顶点集是图G的顶点集的一个子集，且G'的边集也是G的边集的一个子集（即G'中的每条边都在G中），则称G'是G的子图。

生成子图是一种特殊的子图，它保留了原图的所有顶点，但可能删除了原图中的一些边。换句话说，如果图G'的顶点集与图G的顶点集完全相同，且G'的边集是G的边集的一个子集，则称G'是G的一个生成子图。生成子图的一个重要特性是，它“生成”了原图的所有顶点，但不一定包含原图的所有边。

连通分量

极大连通子图：子图必须连通，且包含尽可能多的顶点和边

无向图中的极大连通子图称为连通分量

强连通分量

极大强连通子图：子图必须强连通，同时保留尽可能多的边

有向图中的极大强连通子图称为有向图的强连通分量

生成树

连通图的生成树是包含图中全部顶点的一个极小连通子图（边尽可能的少，但要保持连通）

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

生成森林

在非连通图中，连通分量的生成树构成了非连通图的生成森林

边的权、带权图/网

边的权：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。

带权图/网：边上带有权值的图称为带权图，也称网。

带权路径长度：当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

带权图的应用

几种特殊的图：

无向完全图：无向图中任意两个顶点之间都存在边

有向完全图：有向图中任意两个顶点之间都存在方向相反的两条弧

边数很少的图称为稀疏图，反之称为稠密图，没有绝对的界限，一般来说|E| < |V|log|V|时，可以将G视为稀疏图

树：不存在回路，且连通的无向图

有向树：一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树

n个顶点的树，必有n-1条边

n个顶点的图，若 |E|>n-1，则一定有回路

图的存储——邻接矩阵法

邻接矩阵法是一种用于存储图的数据结构，它通过一个二维数组来表示图中顶点之间的关系。对于一个有 n个顶点的图，其邻接矩阵是一个n*n的矩阵，矩阵的元素a[i][j]表示顶点 i 和顶点 j 之间是否存在边（或弧）。如果存在边（或弧），则 a[i][j] 的值通常设置为 1（在加权图中，a[i][j] 的值为相应的权重），否则设置为 0。对于无向图，邻接矩阵是对称的，即a[i][j]=a[j][i]。而对于有向图，邻接矩阵可能不对称，a[i][j]和a[j][i]分别表示从顶点 i 到顶点 j 和从顶点 j 到顶点 i 的有向边

邻接矩阵法

结点数为n的图G = (V, E)的邻接矩阵A是n*n的。将G的顶点编号为v~1~， v~2~，…，v~n~ ，若A[i][j]=1,则（v~i~，v~j~）或\<v~i~，v~j~>是E（G）中的边，若A[i][j]=0,则（v~i~，v~j~）或\<v~i~，v~j~>不是E（G）中的边

无向图中，第i个结点的度 = 第i行（或第i列）的非零元素个数

有向图中，第i个结点的出度=第i行的非零元素个数，第i个结点的入度=第i列的非零元素个数，第i个结点的度=第i行、第i列的非零元素个数之和

邻接矩阵法求顶点的度/出度/入度的时间复杂度为 O(|V|)

邻接矩阵法存储带权图（网）

邻接矩阵法存储带权图（网）

邻接矩阵法的性能分析

空间复杂度：O(|V|^2^) ——只和顶点数相关，和实际的边数无关

适合用于存储稠密图，无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上三角区/下三角区）

邻接矩阵法的性质

注意：此部分内容建议读者学习完矩阵的乘法后，再学习会比较好，内容虽然简单但是描述很繁琐，此处不展开，读者可以通过王道的视频进行学习，或者与我交流。总结来说，矩阵的 (i,j) 元素表示从顶点 i 到顶点 j 的路径数量，可以通过矩阵自乘来计算更长路径的数量。

邻接矩阵的性质

图的存储——邻接表法

邻接矩阵通过数组实现顺序存储，空间复杂度高，不适合存储稀疏图，邻接表法通过顺序存储和链式存储相结合，实现对结点的存储。邻接表法特别适用于稀疏图（即边的数量远小于顶点的完全配对数）。在邻接表中，图的每个顶点都对应图的一个顶点表项，该顶点表项包含了与该顶点直接相连的所有其他顶点的信息。通常，顶点表项是一个链表，链表中的每个节点代表一个邻接顶点及其相关信息（如边的权重）。

邻接表法

无向图边结点的数量是2|E|，整体空间复杂度为O(|V|+2|E|)，有向图边结点的数量是|E|，整体空间复杂度为O(|V|+|E|)

只要确定了顶点编号，图的邻接矩阵表示方法唯一，图的邻接表示方式并不唯一

邻接表 邻接矩阵
空间复杂度 无向图O(|V|+2|E|)，有向图O(|V|+|E|) O(|V|^2^)
适合用于 存储稀疏图 存储稠密图
表示方式 不唯一 唯一
计算度/出度/入度 计算有向图的度、入度不方便，其余很方便 必须遍历对应行和列
找相邻的边 找有向图的入边不方便，其余很方便 必须遍历对应行和列
图的存储——十字链表

十字链表是一种专门用于存储有向图的数据结构。它结合了邻接表和逆邻接表的特点，为每个顶点维护两个链表：一个链表存储以该顶点为尾节点的边（入边），另一个链表存储以该顶点为头节点的边（出边）。这种结构允许快速访问一个顶点的所有出边和入边，而无需遍历整个图。

十字链表存储有向图

空间复杂度为O(|V|+|E|)，顺着绿色线路即可找到指定顶点的所有出边，顺着橙色的线路即可找到指定顶点的所有入边，注意：十字链表只用于存储有向图

图的存储——邻接多重表

邻接矩阵存储无向图的缺点空间复杂度高O(|V|^2^)，邻接表则每条边对应两分冗余信息，删除顶点、删除边等操作时间复杂度高

邻接多重表是一种用于存储无向图的数据结构，它是邻接表的改进形式。在邻接多重表中，每条边用一个边表结点表示，这个结点同时连接到两个顶点的链表中，分别表示该边的两个方向。这样，每条边在邻接多重表中只存储一次，而不是像在普通邻接表中那样存储两次（一次在每个顶点的链表中）。邻接多重表能够有效解决无向图中边重复存储的问题，并且便于执行一些操作，如查找边、设置边的标记或删除边等

邻接多重表存储无向图

空间复杂度为O(|V|+|E|)，即每条边只对应一份数据，删除边、删除节点等操作很方便，注意：邻接多重表只适用于存储无向图

邻接矩阵 邻接表 十字链表 链接多重表
空间复杂度 O(|V|^2^) 有向图：O(|V|+2|E|)
无向图：O(|V|+|E|)		 O(|V|+|E|) O(|V|+|E|)
找相邻的边 遍历对应行或列
时间复杂度为O(|V|)		 找有向图的入边必须遍历整个邻接表 很方便 很方便
删除边或顶点 删除边很方便，删除顶点需要移动大量数据 无向图中删除边或顶点都不方便 很方便 很方便
适用于 稠密图 稀疏图和其他 只能存有向图 只能存无向图
表示方式 唯一 不唯一 不唯一 不唯一
图的基本操作
函数 作用
Adjacent(G,X,Y) 判断图G是否存在边<x,y>或(x,y)
Neighbors(G,x) 列出图G中与结点x邻接的边
InsertVertex(G,x) 在图G中插入顶点x
DeleteVertex(G,x) 在图G中删除顶点x
AddEdge(G,x,y) 若有向边<x,y>或无向边(x,y)不存在，则向图G中添加该边
RemoveEdge(G,x,y) 若有向边<x,y>或无向边(x,y)存在，则从图G中删除该边
FirstNeighbor(G,x) 求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1
NextNeighbor(G,x,y) 假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1
Get_edge_value(G,x,y) 获取图G中边(x,y)或<x,y>对应的权值
Set_edge_value(G,x,y,v) 设置图G中边(x,y)或<x,y>对应的权值为v
图的广度优先遍历（BFS）

广度优先遍历（Breadth-First Search, BFS）是一种用于遍历或搜索树或图的算法。它从根节点开始，逐层探索图的节点，直到达到叶子节点为止。BFS确保在访问图中的任意一个节点之前，先访问与其最近的节点。这种算法通常使用队列数据结构来实现，因为队列能够按照先进先出（FIFO）的原则管理待访问的节点集合。

BFS

bool visited[MAX_VERTEX_NUM]; //初始都为false，访问标记数组

//广度优先遍历
void BFS(Graph G,int v){ //从顶点v出发，广度优先遍历图G
    visit(v); //访问初始顶点v
    visited[v]=TURE;  //标记已访问的顶点v
    EnQueue(Q,v);  //顶点v入队列Q
    while (!isEmpty(Q)){
        DeQueue(Q,v);  //顶点v出队
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
            if(!visited[w]){  //w为v的尚未访问的邻接顶点
                visit(w);  //访问顶点w
                visited[w]=TURE;  //标记已访问的顶点
                EnQueue(Q,w);  //顶点w入队
            }
    }
}

同一个图的邻接矩阵表示方式唯一，因此广度优先遍历序列唯一。同一个图的邻接表表示方式不唯一，因此广度优先遍历序列不唯一。

上述算法仍存在缺点，如果是非连通图，则无法遍历完所有结点，添加BFSTraverse方法，遍历所有的顶点，对每个连通分量调用一次BFS

void BFSTraverse(Graph G){
    for(i=0;i<G.vexnum;++i)
        visited[i]=FALSE;  //访问标记数组初始化
    InitQueue(Q);  //初始化辅助队列
    for(i=0;i<G.vexnum;++i)  //从0号顶点开始遍历
        if(!visited[i]) //对每个连通分量调用一次BFS
            BFS(G,i);
}

对于⽆向图，调⽤BFS函数的次数=连通分量数

空间复杂度在最坏的情况下，辅助队列大小为O(|V|)，邻接矩阵存储的图，访问|V|个顶点需要O(|V|)的时间，查找每个顶点的邻接点都需要O(|V|)的时间，而总共有|V|个顶点，时间复杂度为O(|V|^2^)。邻接表存储的图，访问|V|个顶点需要O(|V|)的时间，查找各个顶点的邻接点共需要O(|E|)的时间，时间复杂度为O(|V|+|E|)

广度优先生成树由广度优先遍历过程确定。由于邻接表的表示方式不唯一，因此基于邻接表的广度优先生成树也不唯一。对于非连通图的广度优先遍历，可得到广度优先生成森林

图的深度优先遍历（DFS）

深度优先遍历（DFS）是一种用于图或树的遍历算法，它尝试深入探索图的分支。算法的基本思想是从一个顶点开始，尽可能深地进入图的一个分支，访问所有可达的顶点，直到遇到没有未访问邻居的顶点为止，然后回溯到上一个顶点，继续探索其他未访问的分支。DFS可以使用递归或非递归（使用栈）的方式实现。

深度优先遍历的步骤

  1. 访问初始顶点，并将其标记为已访问。
  2. 选择一个未被访问的邻接顶点，并将其标记为已访问。
  3. 递归地对新访问的顶点执行深度优先遍历。
  4. 如果当前顶点没有未访问的邻接顶点，则回溯到上一个顶点。
  5. 重复步骤2至4，直到所有顶点都被访问或者达到递归的基准情况。
bool visited[MAX_VERTEX_NUM]; //初始都为false，访问标记数组

void DFSTraverse(Graph G){
    for(i=0;i<G.vexnum;++i)
        visited[i]=FALSE;  //访问标记数组初始化
    InitQueue(Q);  //初始化辅助队列
    for(i=0;i<G.vexnum;++i)  //从0号顶点开始遍历
        if(!visited[i]) //对每个连通分量调用一次BFS
            DFS(G,i);
}
//深度优先遍历
void DFS(Graph G,int v){ //从顶点v出发，广度优先遍历图G
    visit(v); //访问初始顶点v
    visited[v]=TURE;  //标记已访问的顶点v
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
        if(!visited[w]){  //w为v的尚未访问的邻接顶点
            DFS(G,w);
            }
}

空间复杂度来自函数调用栈，最坏情况，递归深度为O(|V|)，最好情况空间复杂度为O(1)。邻接矩阵存储的图，访问|V|个顶点需要O(|V|)的时间，查找每个顶点的邻接点都需要O(|V|)的时间，而总共有|V|个顶点，时间复杂度为O(|V|^2^)。邻接表存储的图，访问|V|个顶点需要O(|V|)的时间，查找各个顶点的邻接点共需要O(|E|)的时间，时间复杂度为O(|V|+|E|)

同一个图的邻接矩阵表示方式唯一，因此深度优先遍历序列唯一。同一个图的邻接表表示方式不唯一，因此深度优先遍历序列不唯一。

对⽆向图进⾏BFS/DFS遍历，调⽤BFS/DFS函数的次数=连通分量数。对于连通图，只需调⽤1次 BFS/DFS。对有向图进⾏BFS/DFS遍历，调⽤BFS/DFS函数的次数要具体问题具体分析，若起始顶点到其他各顶点都有路径，则只需调⽤1次BFS/DFS 函数，对于强连通图，从任⼀结点出发都只需调⽤1次 BFS/DFS

图的应用
最小生成树（最小代价树）

对于⼀个带权连通⽆向图G = (V, E)，⽣成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设R为G的所有⽣成树的集合，若T为R中边的权值之和最⼩的⽣成树，则T称为G的最⼩⽣成树（Minimum-Spanning-Tree, MST）。最⼩⽣成树可能有多个，但边的权值之和总是唯⼀且最⼩的。最⼩⽣成树的边数 = 顶点数 - 1。砍掉⼀条则不连通，增加⼀条边则会出现回路。

如果⼀个连通图本身就是⼀棵树，则其最⼩⽣成树就是它本身。只有连通图才有⽣成树，⾮连通图只有⽣成森林。

Prim 算法（普⾥姆）：从某⼀个顶点开始构建⽣成树；每次将代价最⼩的新顶点纳⼊⽣成树，直到所有顶点都纳⼊为⽌。时间复杂度为O(|V|^2^)，适用于边稠密图

Kruskal 算法（克鲁斯卡尔）：每次选择⼀条权值最⼩的边，使这条边的两头连通（原本已经连通的就不选），直到所有结点都连通。时间复杂度为O(|E|log~2~|E|)，适用于边稀疏图

最短路径-BFS算法

广度优先搜索（Breadth-First Search, BFS）算法是一种用于图或树的遍历算法，它从根节点开始，逐个访问相邻节点，并将这些节点排队等待处理。在最短路径问题中，BFS算法可以用来找到从单一源点到其他所有点的最短路径，特别是当图中所有边的权重相同（即边长为1）时，BFS能够有效地找到最短路径。

//求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G,int u){
    //d[i]表示从u到i结点的最短路径
    for(i=0;i<G.vexnum;++i)
    {
        d[i]=NULL;  //初始化路径长度
        path[i]=-1;  //最短路径从哪个顶点过来
    }
    d[u]=0;
    visited[u]=TRUE;
    EnQueue(Q,u);
    while(!isEmpty(Q))
    {
        DeQueue(Q,u);
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
            if(!visited[w])
            {
                d[w]=d[u]+1;  //路径长度加1
                path[w]=u;  //最短路径应该从u到w
                visited[w]=TRUE;
                EnQueue(Q,w);  //顶点w入队
            }
    }
}
最短路径-Dijkstra算法

Dijkstra算法是一种用于求解具有非负权重边的图中单源最短路径问题的算法。该算法采用贪心策略，逐步构建最短路径树，直到找到源点到图中所有其他顶点的最短路径。算法的核心思想是维护一个优先队列，其中包含了到目前为止已知的最短路径估计值，并在每次迭代中选择具有最小估计值的顶点进行扩展。

Dijkstra算法步骤

  1. 初始化：将源点的最短路径估计值设为0，其余所有顶点的最短路径估计值设为无穷大。同时，将所有顶点标记为未访问。

  2. 建立优先队列：创建一个优先队列，用于存放当前已知的最短路径估计值及其对应的顶点。

  3. 迭代过程：

    从优先队列中取出具有最小最短路径估计值的顶点，将其标记为已访问。

    更新该顶点所有未访问邻接顶点的最短路径估计值，如果通过当前顶点到邻接顶点的路径比直接路径更短。

    将更新后的邻接顶点重新加入优先队列。

  4. 重复步骤3，直到所有顶点都被访问或者优先队列为空。

Dijkstra算法

Dijkstra算法无法解决带负权值带权图，算法总空间复杂度为O(|V|^2^)

最短路径-Floyd算法

Floyd算法（也称为Floyd-Warshall算法）是一种动态规划算法，用于计算加权图中所有顶点对之间的最短路径。该算法不仅适用于有向图，也适用于带负权边的图，但不能处理存在负权回路的图。Floyd算法的核心思想是通过迭代地考虑图中的每个顶点作为中间点，来更新顶点对之间的最短路径估计值。

Floyd算法步骤

  1. 初始化：创建一个二维数组 dist，用于存储顶点对之间的最短路径估计值。对于图中的每对顶点 (i, j)，如果存在直接边，则 dist[i][j] 初始化为该边的权重；如果不存在直接边，则 dist[i][j] 初始化为无穷大。同时，创建一个二维数组 next，用于记录达到每个顶点的前一个顶点的信息。
  2. 迭代更新：算法通过三层嵌套循环进行迭代更新。外层循环选择中间顶点 k，中层循环选择源顶点 i，内层循环选择目标顶点 j。对于每一组 (i, k, j)，检查通过中间顶点 k 的路径 (i, k) 和 (k, j) 的总权重是否小于现有的最短路径 (i, j)。如果是，则更新 dist[i][j] 和 next[i][j]。
  3. 终止条件：当所有顶点对都经过了迭代更新后，算法结束。此时，dist 数组中存储的就是所有顶点对之间的最短路径估计值。

Floyd代码

Floyd 算法不能解决带有"负权回路"的图（有负权值的边组成回路），这种图有可能没有最短路径

三种算法对比

有向无环图

有向⽆环图：若⼀个有向图中不存在环，则称为有向⽆环图，简称DAG图（Directed Acyclic Graph）

有向无环图的特点

  • 无环性：图中不存在任何闭合的路径，即从一个顶点出发，经过一系列有向边最终回到原点的路径。

  • 有向性：图中的边都具有方向，从一个顶点指向另一个顶点，表示两个顶点之间的单向关系。

有向无环图的应用

有向无环图在计算机科学和数据结构中有着广泛的应用，例如：

  • 任务调度：在项目管理中，有向无环图可以用来表示任务之间的依赖关系，帮助确定任务的执行顺序。

  • 编译原理：编译器使用有向无环图来表示依赖关系，以便进行优化和代码生成。

  • 数据流分析：在编译器设计中，数据流分析常常涉及到有向无环图的构建和分析。

  • 版本控制系统：如Git，内部使用有向无环图来管理文件的历史版本和分支。

拓扑排序
AOV网

AOV⽹(Activity On Vertex NetWork，⽤顶点表示活动的网），⽤DAG图（有向⽆环图）表示⼀个⼯程。顶点表示活动，有向边<V~i~, V~j~>表示活动V~i~必须先于活动V~j~进⾏。

拓扑排序：在图论中，由⼀个有向⽆环图的顶点组成的序列，当且仅当满⾜下列条件时，称为该图的⼀个拓扑排序：

① 每个顶点出现且只出现⼀次。

② 若顶点A在序列中排在顶点B的前⾯，则在图中不存在从顶点B到顶点A的路径。

或者定义为：拓扑排序是对有向⽆环图的顶点的⼀种排序，它使得若存在⼀条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后⾯。每个AOV⽹都有⼀个或多个拓扑排序序列。

拓扑排序的实现：

① 从AOV⽹中选择⼀个没有前驱（⼊度为0）的顶点并输出。

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

③ 重复①和②直到当前的AOV⽹为空或当前⽹中不存在⽆前驱的顶点为⽌。

拓扑排序实现

逆拓扑排序，相比之前的DFS算法，增加一个打印输出即可

逆拓扑排序

关键路径
AOE网

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如 完成活动所需的时间），称之为⽤边表示活动的⽹络，简称AOE⽹ (Activity On Edge NetWork)

AOE⽹具有以下两个性质：

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

② 只有在进⼊某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发⽣。 另外，有些活动是可以并⾏进⾏的

在AOE⽹中仅有⼀个⼊度为0的顶点，称为开始顶点（源点），它表示整个⼯程的开始；也仅有⼀个出度为0的顶点，称为结束顶点（汇点），它表示整个⼯程的结束。从源点到汇点的有向路径可能有多条，所有路径中，具有最⼤路径⻓度的路径称为关键路径，⽽把关键路径上的活动称为关键活动。完成整个⼯程的最短时间就是关键路径的⻓度，若关键活动不能按时完成，则整个⼯程的完成时间就会延⻓。

事件v~k~的最早发⽣时间ve(k)：决定了所有从v~k~开始的活动能够开⼯的最早时间。

活动a~i~的最早开始时间e(i)：指该活动弧的起点所表⽰的事件的最早发⽣时间。

事件v~k~的最迟发⽣时间vl(k)：它是指在不推迟整个⼯程完成的前提下，该事件最迟必须发⽣的时间。

活动a~i~的最迟开始时间l(i)：它是指该活动弧的终点所表示事件的最迟发⽣时间与该活动所需时间之差。

活动a~i~的时间余量d(i)=l(i)-e(i)，表⽰在不增加完成整个⼯程所需总时间的情况下，活动ai可以拖延的时间 若⼀个活动的时间余量为零，则说明该活动必须要如期完成，d(i)=0即l(i) = e(i)的活动ai是关键活动由关键活动组成的路径就是关键路径

所有事件的最早发生时间

所有事件最迟发生时间

所有活动最早发生时间

所有活动最迟发生时间

所有活动时间余量关键活动、关键路径

若关键活动耗时增加，则整个工程的工期将增加。缩短关键活动的时间，可以缩短整个⼯程的⼯期。当缩短到⼀定程度时，关键活动可能会变成⾮关键活动。可能有多条关键路径，只提⾼⼀条关键路径上的关键活动速度并不能缩短整个⼯程的⼯期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短⼯期的⽬的。