《数据结构》第六章图

Article

数据结构

6.1 图的基本概念

6.1.1 图的定义

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

1. 有向图

若 $E$ 是有向边（也称弧）的有限集合时，则图 $G$ 为有向图。

$v$ - 弧尾
$w$ - 弧头
$<v,w>$ - 从 v 到 w 的弧，也称 v 邻接到 w。

2. 无向图

若 $E$ 是无向边（简称边）的有限集合时，则图 $G$ 为无向图。

$v$ 和 $w$ 互为邻接点
可记作 $(v,w)$ 或 $(w,v)$。

3. 简单图、多重图

简单图
- 不存在重复边。
- 不存在顶点到自身的边。
多重图
- 某两个结点之间的边数多于一条。
- 又允许顶点通过同一条边和自己关联。

4. 顶点的度、入度和出度

顶点的度
- 无向图 - 指依附于该顶点的边的条数，记作 $TD(v_i)$。
  - 无向图的全部顶点的度的和等于边数的2倍。$\sum_{i = 1}^{n} TD(v_i)=2e$
- 有向图 - 其入度和出度之和，即 $TD(v) = ID(v)+OD(v)$。
  - 在具有 $n$ 个顶点、$e$ 条边的有向图中，入度=出度=边数。$\sum_{i = 1}^{n} ID(v_i)=\sum_{i = 1}^{n} OD(v_i)=e$
入度（有向图）- 以顶点 $v$ 为终点的有向边的数目，记作 $ID(v)$。
出度（有向图）- 以顶点 $v$ 为起点的有向边的数目，记作 $OD(v)$。

5. 路径、路径长度和回路

路径 - 顶点 $v_p$ 到 $v_q$ 之间的一条路径的顶点序列：$v_p,v_{i1},v_{i2},...,v_q$
路径长度 - 一条路径上边的数目。
回路 - 第一个顶点和最后一个顶点相同的路径称为回路或环。
- 若一个图有 $n$ 个顶点，且有大于 $n-1$ 条边，则此图必有回路。

6. 简单路径、简单回路

简单路径 - 在路径序列中，顶点不重复出现的路径。
简单回路 - 除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。

7. 距离

对于顶点 $u$ 和顶点 $v$

若存在最短路径，则路径长度为：从 $u$ 到 $v$ 的距离。
若不存在路径，则距离为无穷（$\infty$）

8. 子图

子图
- 两个图 $G = (V, E)$ 和 $G^{'} = (V^{'}, E^{'})$ ，若 $V^{'}$ 是 $V$ 的子集，且 $E^{'}$ 是 $E$ 的子集，则称 $G^{'}$ 是 $G$ 的子图。
生成子图
- 满足 $V(G^{'})=V(G)$ 的子图 $G^{'}$。也就是 $G^{'}$ 包含原图的所有顶点。

9. 连通、连通图和连通分量

连通
- 在无向图中，从顶点 $v$ 到顶点 $w$ 有路径存在，则称 $v$ 和 $w$ 是连通的。
连通图
- 图中任意两个顶点都是连通的，则称该图为连通图。
- 对于 $n$ 个顶点的无向图：
  - 若是连通图，则最少有 $n-1$ 条边。
  - 若是非连通图，则最多可能有 $C_{n-1}^{2}$ 条边。
连通分量
- 无向图中的极大连通子图称为连通分量。
- 极大连通子图 - 子图必须连通，且包含尽可能多的顶点和边。

10. 强连通图、强连通分量

强连通
- 在有向图中，从顶点 $v$ 到顶点 $w$ 和从顶点 $w$ 到顶点 $v$ 有路径存在，则称这两个顶点是强连通的。
强连通图
- 图中任何一对顶点都是强连通的，则称此图为强连通图。
- 对于 $n$ 个顶点的有向图：
  - 若是强连通图，则最少有 $n$ 条边（形成回路）。
强连通分量
- 有向图中的极大强连通子图称为有向图的强连通分量。
- 极大强连通子图 - 子图必须强连通，同时保留尽可能多的边。

11. 生成树、生成森林

生成树
- 包含图中全部顶点的一个极小连通子图。
- 若图中顶点数为 $n$ ，则它的生成树含有 $n-1$ 条边。
生成森林
- 在非连通图中，连通分量的生成树构成了非连通图的生成森林。

12. 边的权、网和带权路径长度

边的权
- 每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
网（带权网）
- 边上带有权值的图称为带权图，也称网。
带权路径长度
- 当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度。

13. 完全图（也称简单完全图）

无向完全图
- 无向图中任意两个顶点之间都存在边。
- 若无向图的顶点数 $|V|=n$ ，则有 $C_{n}^{2}=\frac{n(n-1)}{2}$ 条边的无向图称为无向完全图。
有向完全图
- 有向图中任意两个顶点之间都存在方向相反的两条弧。
- 若有向图的顶点数 $|V|=n$ ，则有 $2\times C_{n}^{2}=n(n-1)$ 条边的有向图称为完全图。

14. 稠密图、稀疏图

稠密图
- 边数很少的图。
稀疏图
- 边数很多的图。

15. 有向树

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

6.2 图的存储及基本操作

6.2.1 邻接矩阵法

用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息。

♾️ C 代码:

#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
typedef struct {
    VertexType vex[MaxVertexNum];
    EdgeType edge[MaxVertexNum][MaxVertexNum];
    int vexnum,arcnum;//顶点数和边数
}

求顶点的度、出度、入度的时间复杂度：$O(|V|)$，空间复杂度： $O(|V|^2)$

特点
- 无向图的邻接矩阵一定是一个对称矩阵（并且唯一），实际存储只需存储上（或下）三角矩阵的元素（见第三章3.4.3）。
- 顶点的度计算
  - 对于无向图，矩阵的第 $i$ 行（或第 $i$ 列）非零元素的个数 = 顶点 $i$ 的度 $TD(v_{i})$。
  - 对于有向图，矩阵的第 $i$ 行非零元素的个数为出度 $OD(v_i)$ ，第 $i$ 列非零元素的个数为入度 $IN(v_i)$。
- 稠密图适合采用邻接矩阵的存储表示。
- $A^n[i][j]$ 的含义
  - 矩阵的n方 $A^n[i][j]$表示：顶点 $i$ 到顶点 $j$ 长度为 $n$ 的路径的数目。

6.2.2 邻接表法

使用顺序存储和链式存储（类似树的孩子表示法），减少不必要的浪费。

♾️ C 代码:

#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;
}ALGraph;

求顶点的度、出度、入度的时间复杂度：$O(|V|+|E|)$，空间复杂度： $O(|V|+|E|)$。

6.2.3 十字链表

会看图即可
只用于存储有向图。

空间复杂度：$O(|V|+|E|)$

6.2.4 邻接多重表

会看图即可
只用于存储无向图。

空间复杂度：$O(|V|+|E|)$

6.2.5 图的四种存储方式的总结

	邻接矩阵	邻接表	十字链表	邻接多重表
空间复杂度	$O(\mid V\mid ^2)$	无向图：$O(\mid V\mid +2\mid E\mid)$ 有向图：$O(\mid V\mid +\mid E\mid)$	$O(\mid V\mid +\mid E\mid)$	$O(\mid V\mid +\mid E\mid)$
找相邻边	遍历对应行或列的时间复杂度为$O(\mid V\mid)$	找有向图的入度必须遍历整个邻接表	很方便	很方便
删除边或顶点	删除边很方便，删除顶点需要大量移动数据	无向图中删除边或顶点都不方便	很方便	很方便
适用于	稠密图	稀疏图或其他	只能存有向图	只能存无向图
表示方式	唯一	不唯一	不唯一	不唯一

6.2.6 图的基本操作

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)：在图 G 中增加边(x, y)或<x, y>，前提该边在图中不存在。
RemoveEdge(G, x, y)：在图 G 中删除边(x, y)或<x, y>，前提该边在图中存在。
FirstNeighbor(G, x)：求图 G 中顶点 x 的第一个邻接点，若有则返回顶点号。
NextNeighbor(G, x, y)：顶点 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。

6.3 图的遍历

6.3.1 广度优先搜索

1. BFS算法

BFS要点（使用队列实现）
- 找到与一个顶点相邻的所有顶点
- 标记哪些顶点被访问过
- 需要一个辅助队列 visited[]，初始都为false

代码实现

♾️ C 代码:

bool visited[MAX_VERTEX_NUM];

void BFSTraverse(Graph G){
  for(int i = 0;i<G.vexnum;++i)
      visited[i] = 0;
  InitQueue(Q);
  for(int i = 0;i<G.vexnum;++i)
      if(!visited[i])
          BFS(G, i);
}

使用邻接表实现

♾️ C 代码:

void BFS(ALGraph G, int i){
  visit(i);
  visited[i] = TRUE;
  EnQueue(Q, i);
  while(!IsEmpty(Q)){
      DeQueue(Q, v);
      for(p = G.vertices[v].firstarc; p ;p = p->nextarc){
          w = p->adjvex;
          if(visited[w] == FLASE){
              visit(w);
              visited[w] = TRUE;
              EnQueue(Q, w);
          }
      }
  }
}

时间复杂度：$O(|V|+|E|)$

使用邻接矩阵实现

♾️ C 代码:

void BFS(MGraph G, int i){
  visit(i);
  visited[i] = TRUE;
  EnQueue(Q, i);
  while(!IsEmpty(Q)){
      DeQueue(Q, v);
      for(w = 0;w<G.vexnum;w++){
          if(visited[w] == FALSE && G.edge[v][w] == 1){
              visit(w);
              visited[w] == TRUE;
              EnQueue(Q, w);
          }
      }
  }
}

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

2. 广度优先生成树

在 BFS 的过程中，可以得到一颗遍历树，称为广度优先生成树。

使用邻接矩阵存储的生成树是唯一的。
使用邻接表存储的生成树不是唯一的。
对于非连通图的BFS，会生成森林。

6.3.2 深度优先搜索

1. DFS算法

对于 DFS，使用递归栈实现，类似于树的先序遍历。

代码实现

♾️ C 代码:

bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G){
  for(int i = 0; i<G.vexnum; i++)
      visited[i] == FALSE;
  for(int i = 0; i<G.vexnum; i++)
      if(!visited[i])
          DFS(G, i);
}

邻接表实现

♾️ C 代码:

void DFS(ALGraph G, int i){
  visit(i);
  visited[i] = TRUE;
  for(p = G.vertices[i].firstarc; p ;p = p->nextarc){
      int j = p->adjvex;
      if(visited[j] == FALSE)
          DFS(G, j);
  }
}

时间复杂度：$O(|V|+|E|)$

邻接矩阵实现

♾️ C 代码:

void DFS(MGraph G, int i){
  visit(i);
  visited[i] = TRUE;
  for(int j = 0; j<G.vexnum; j++){
      if(visited[j] == FLASE && G.edge[i][j] == 1)
          DFS(G, j);
  }
}

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

2. 深度优先生成树

在 DFS 的过程中，可以得到一颗遍历树，称为深度优先生成树。

使用邻接矩阵存储的生成树是唯一的。
使用邻接表存储的生成树不是唯一的。
对于非连通图的DFS，会生成森林。

6.3.3 图的遍历与图的连通性

对无向图进行 BFS/DFS 遍历
- 调用 BFS/DFS 函数的次数 = 连通分量数
- 对于连通图，只需调用 1 次
对有向图进行 BFS/DFS 遍历
- 调用 BFS/DFS 函数的次数要具体问题具体分析
- 若起始顶点到其他各顶点都有路径，则只需调⽤ 1 次 BFS/DFS 函数
- 对于强连通图，从任一结点出发都只需调用 1 次。
- 判断有向图是否有环，可采用“深度优先搜索”或“拓扑排序”。

6.4 图的应用

6.4.1 最小生成树

1. 定义及性质

对于⼀个带权连通⽆向图，权值之和最小的那棵生成树称为最小生成树。

性质
- 若图中存在权值相同的边，则最小生成树可能不唯一。
- 若图中不存在权值相同的边，则最小生成树唯一。
- 若图本身就是一棵树时（边比顶点少 1 ），则最小生成树就是其本身。
- 最小生成树可能有多个，但边的权值之和总是唯一且最小的。
- 最小生成树的边数 = 顶点数 - 1。

2. Prime 算法

要点
- 从某⼀个顶点开始构建⽣成树
- 每次将权值最⼩的新顶点纳⼊⽣成树
- 直到所有顶点都纳⼊为⽌
时间复杂度
- $O(|V|^2)$
- 不依赖 $|E|$，因此适用于求解边稠密的图的最小生成树。

3. Kruskal 算法

要点
- 每次选择⼀条权值最⼩的边
- 使这条边的两头连通（原本已经连通的就不选）
- 直到所有结点都连通
时间复杂度
- $O(|E|\log_{2}{|E|})$
- 不依赖 $|V|$，因此适用于求解边稀疏而顶点多的图的最小生成树。

6.4.2 最短路径

1. BFS算法求解单源最短路径

适用无权图

使用邻接表为例

♾️ C 代码:

void BFS_MIN_Distance(Graph G, int u){
  //d[i]表示从 u 到 i 结点的最短路径
  for(int i = 0; i<G.vexnum; ++i){
      d[i] = ∞;
      //path[i] = -1   //也可以使用path数组记录最短路径的顶点
  }
  visited[u] = TRUE;
  d[u] = 0;
  EnQueue(Q, u);
  while(!IsEmpty(Q)){
      DeQueue(Q, u);
      for(p = G.vertices[u].firstarc; p ;p = p->nextarc){
          w = p->adjvex;
          if(visited[w] == FLASE){
              visited[w] = TRUE;
              d[w] = d[u] + 1;
              //path[w] = u;
              EnQueue(Q, w);
          }
      }
  }
}

同理，使用邻接矩阵时，可以在其代码基础上修改 d[]和 path[]。

时间复杂度
- 邻接表：$O(|V|+|E|)$
- 邻接矩阵：$O(|V|^2)$

2. Dijkstra算法求解单源最短路径

初始：从 $V_0$ 开始，初始化三个数组信息
- final[]：标记各顶点是否已找到最短路径。找到则TRUE，没找到则FALSE
- dist[]：最短路径长度
- path[]：路径上的前驱
接下来每一轮（n-1轮），检查所有邻接⾃ $V_i$ 的顶点，若其 final 值为FALSE，则更新 dist 和 path 信息。
时间复杂度：$O(|V|^2)$
对于有负边的权值，Dijikstra算法不一定能找到正确的结果。

3. Floyd算法求解各顶点之间最短路径

算法核心思想是：求出每一对顶点之间的最短路径。使用动态规划的思想，将问题求解分为多个阶段。

对于 n 个顶点的图，求任意一对顶点 $V_i$ 到 $V_j$ 之间的最短路径，分为以下几个阶段：
- 初始（-1）：不允许在其他顶点中转，求出任意一对顶点的最短路径
- 0：允许在 $V_0$ 中转，求最短路径
- 1：允许在 $V_0、V_1$ 中转，求最短路径
- 2：允许在 $V_0、V_1、V_2$ 中转，求最短路径
- ……
- n-1：允许在 $V_0、V_1、V_2、……、V_{n-1}$ 中转，求最短路径
时间复杂度：$O(|V|^3)$
Floyd算法允许图中有带负权值的边，但不允许包含总权值为负的回路。

4. 三种算法的总结

	BFS算法	Dijikstra算法	Floyd算法
用途	求单源最短路径	求单源最短路径	求各顶点之间的最短路径
无权图	适用	适用	适用
带权图	不适用	适用	适用
带负权值的图	不适用	不适用	适用
带负权回路的图	不适用	不适用	不适用
时间复杂度	邻接表：$O(\mid V\mid +\mid E\mid)$ 邻接矩阵：$O(\mid V\mid ^2)$	$O(\mid V\mid ^2)$	$O(\mid V\mid ^3)$
注：也可以用 Dijikstra算法求所有顶点间的最短路径，重复 $	V	$ 次即可，时间复杂度也是$O(	V	^3)$

6.4.3 有向无环图描述表达式

有向⽆环图：若⼀个有向图中不存在环，则称为有向⽆环图，简称DAG图。
对于含有公共子式的表达式，可以合并公共子式，将其变成有向无环图，解题步骤：
- Step 1：把各个操作数不重复地排成⼀排
- Step 2：标出各个运算符的⽣效顺序
- Step 3：按顺序加⼊运算符，注意“分层”
- Step 4：从底向上逐层检查同层的运算符是否可以合体

6.4.4 拓扑排序

1.拓扑排序

AOV网：⽤DAG图（有向⽆环图）表示⼀个⼯程。顶点表示活动，有向边 $<V_i, V_j>$ 表示活动 $V_i$ 必须先于活动 $V_j$ 进⾏。
拓扑排序：由⼀个有向⽆环图的顶点组成的序列，满足以下条件：
- 每个顶点出现且只出现一次
- 顶点 A 在序列中排在顶点 B 前面，则图中不存在 B 到 A 的路径。（无环）

每个 AOV网都有一个或多个拓扑排序序列（入度为1的顶点有多个时）。

♾️ C 代码:

bool ToplogicalSort(Graph G){
  InitStack(S);
  int i;
  for(i = 0; i<G.vexnum; i++)
      if(indegree[i] == 0)
          Push(S, i);  //将所有入度为0的顶点入栈
  int count = 0;  //记录当前已经输出的顶点数
  while(!IsEmpty(S)){
      Pop(S, i);  //入度为0的顶点出栈
      printf[count++] = i; //记录拓扑序列
      
      //逻辑上删边
      for(p = G.vertices[i].firstarc; p ;p = p->nextarc){
      //将所有i指向的顶点的入度-1，并将入度减为0的顶点入栈
          v = p->adjvex;
          if(!(--indegree[v]))
              Push(S, v);
      }
  }
  if(count < G.vexnum)
      return false;  //排序失败，图中有回路
  else
      return true;
}

邻接表存储时的时间复杂度：$O(|V|+|E|)$
邻接矩阵存储时的时间复杂度：$O(|V|^2)$

2.逆拓扑排序

对于逆拓扑排序，考虑顶点的出度是否为0即可，建议使用邻接矩阵存储方式。

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

♾️ C 代码:

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_Topo(Graph G, int v){
  visited[v] = TRUE;
  for(w = G.vertices[i].firstarc; w ;w = w->nextarc){
      int w = w->adjvex;
      if(visited[w] == FALSE)
          DFS(G, w);
  }
  
  print(v);  //输出顶点
}

6.4.5 关键路径

1. AOE网

AOE网：在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销。
源点：仅有⼀个⼊度为0的顶点，称为开始顶点（源点），它表示整个⼯程的开始。
汇点：仅有⼀个出度为0的顶点，称为结束顶点（汇点），它表示整个⼯程的结束。
性质
- 只有在某顶点所代表的事件发⽣后，从该顶点出发的各有向边所代表的活动才能开始
- 只有在进⼊某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发⽣。
- 另外，有些活动是可以并⾏进⾏的。
关键路径：从源点到汇点的有向路径可能有多条，所有路径中，具有最⼤路径⻓度的路径。
关键活动：关键路径上的活动。

2. 事件$v_k$的最早发生时间$v_e(k)$

$v_e(源点)=0$
$v_e(k)=Max\{ v_e(j)+Weight(v_j,v_k)\}$，$v_k$ 为 $v_j$ 的任意后继，$Weight(v_j,v_k)$ 为$<v_j,v_k>$的权值。

3. 事件$v_k$的最晚发生时间$v_l(k)$

$v_l(汇点)=v_e(汇点)$
$v_l(k)=Min\{ v_l(j)+Weight(v_k,v_j)\}$，$v_k$ 为 $v_j$ 的任意前驱。

4. 活动$a_i$的最早开始时间$e(i)$

若 $<v_k,v_j>$表示活动 $a_i$，则有 $e(i)=v_e(k)$

5. 活动$a_i$的最晚开始时间$l(i)$

若 $<v_k,v_j>$表示活动 $a_i$，则有 $l(i)=v_l(j)-Weight(v_k,v_j)$

6. 时间余量 $d(i)=l(i)-e(i)$

当 $d(i)=0$时，表示活动 $a_i$ 是关键活动

7. 缩短工期分析

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

6.4.6 各种图算法使用不同存储结构的时间复杂度

	Dijikstra	Floyd	Prim	Kruskal	DFS	BFS	拓扑排序	关键路径
邻接矩阵	$O(n^2)$	$O(n^3)$	$O(n^2)$	-	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(n^2)$
邻接表	-	-	-	$O(e\log_{2}{e})$	$O(n+e)$	$O(n+e)$	$O(n+e)$	$O(n+e)$

现在已有 147 次阅读，0 条评论，0 人点赞

日	一	二	三	四	五	六
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

《数据结构》第六章 图

6.1 图的基本概念

6.1.1 图的定义

1. 有向图

2. 无向图

3. 简单图、多重图

4. 顶点的度、入度和出度

5. 路径、路径长度和回路

6. 简单路径、简单回路

7. 距离

8. 子图

9. 连通、连通图和连通分量

10. 强连通图、强连通分量

11. 生成树、生成森林

12. 边的权、网和带权路径长度

13. 完全图（也称简单完全图）

14. 稠密图、稀疏图

15. 有向树

6.2 图的存储及基本操作

6.2.1 邻接矩阵法

6.2.2 邻接表法

6.2.3 十字链表

6.2.4 邻接多重表

6.2.5 图的四种存储方式的总结

6.2.6 图的基本操作

6.3 图的遍历

6.3.1 广度优先搜索

1. BFS算法

2. 广度优先生成树

6.3.2 深度优先搜索

1. DFS算法

2. 深度优先生成树

6.3.3 图的遍历与图的连通性

6.4 图的应用

6.4.1 最小生成树

1. 定义及性质

2. Prime 算法

3. Kruskal 算法

6.4.2 最短路径

1. BFS算法求解单源最短路径

2. Dijkstra算法求解单源最短路径

3. Floyd算法求解各顶点之间最短路径

4. 三种算法的总结

6.4.3 有向无环图描述表达式

6.4.4 拓扑排序

1.拓扑排序

2.逆拓扑排序

6.4.5 关键路径

1. AOE网

2. 事件$v_k$的最早发生时间$v_e(k)$

3. 事件$v_k$的最晚发生时间$v_l(k)$

4. 活动$a_i$的最早开始时间$e(i)$

5. 活动$a_i$的最晚开始时间$l(i)$

6. 时间余量 $d(i)=l(i)-e(i)$

7. 缩短工期分析

6.4.6 各种图算法使用不同存储结构的时间复杂度

《数据结构》第六章图