图

• 图
  • 定义
  • 图的存储
    • 临接矩阵
    • 邻接表
    • 十字链表法
    • 邻接多重表
  • 基本操作
  • 图的遍历
    • 广度优先遍历
    • 深度优先遍历
  • 最小生成树
  • 最短路径问题
  • Dijkstra算法
  • Floyd算法
  • 有向无环图(DAG)
  • 拓扑排序
  • 关键路径

定义

图G由顶点集V和边集E组成，记为G=(V, E)，其中V(G) 表示图G中顶点的有限非空集；E(G) 表示图G 中顶点之间的关系（边）集合。若 $V={v_1, v_2, …, v_n}$，则用 $|V|$ 表示图G 中顶点的个数，也称图G 的阶，$E={(u, v)|u\in V, v\in V}$，用 $|E|$ 表示图G中边的条数。

G：Graph
V：Vertex
E：Edge
线性表可以是空表，树可以是空树，但图不可以是空的，即V一定是非空集

e.g.
V:车站，E：铁路

社交软件中的好友关系可以看成是一种无向图
微博中的粉丝关系可以看作是一种有向图

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

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

圆括号对应无向图的边，尖括号对应有向图的边。

简单图：

• 不存在重复边
• 不存在顶点到自身的边

数据结构中一般只讨论简单图。

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

顶点的度

• 对于无向图:顶点v的度是指依附于该顶点的边的条数,记为 TD(v).
• 对于有向图
  • 入度:以顶点v为终点的有向边的数目,记为ID(v)
  • 出度:以顶点v为起点的有向边的数目,记为OD(v)
  • 顶点v的度等于其入度和出度之和,即TD(v)=ID(v)+OD(v)

有n个顶点的无向图的度等于 $\displaystyle\sum_{i=1}^nTD(v_i)=2|E|$
其中 $|E|$ 表示无向图边的数量

在有 n 个顶点的有向图中 $\displaystyle\sum_{i=1}^nID(v_i)=\sum_{i=1}^nOD(v_i)=|E|$

名词:

• 路径
• 回路:第一个顶点和最后一个顶点相同的路径称为回路或环
• 简单路径:在路径序列中,顶点不重复出现的路径称为简单路径
• 简单回路:除第一个顶点和最后一个顶点外,其余顶点不重复出现的回路称为简单回路
• 路径长度:路径上边的数量
• 点到点的距离:从顶点v到顶点w的最短路径若存在,则此路径的长度称为从v到w的距离
• 若从v到w根本不存在路径,则记该距离为无穷(∞)

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

若无向图 G 中任意两个顶点都是连通的,则称图 G 为连通图,否则称为非连通图
若有向图中任何一对顶点都是强连通的,则称此图为强连通图.

考点

• 对于n个顶点的无向图G
  • 若图G是连通图,则最少有n-1条边
  • 若图G是非连通图,则最多可能有$c_{n-1}^2$ 条边
• 对于n个顶点的有向图G
  • 若G是强连通图,则最少有n条边(形成回路)

子图
设有两个图 G=(V, E) 和 G'=(V', E'),若 V' 是 V 的子集,且 E' 是 E 的子集,则称G' 是 G 的子图
(子图的前提要求是G’必须是一个图,并不是随便G的点的子集和边的子集合在一起就是子图,因为边是通过两个点确定的,如果只是取子集的话,可能会出现一条边,但是只有其中一个端点的情况)

生成子图
若子图中的点包含了原图中所有的点,则称其为原图G的生成子图.

连通分量
无向图中的极大连通子图称为连通分量.
子图必须连通,且包含尽可能多的顶点和边

比如: 国家铁路图有三个连通分量

• 大陆铁路网
• 海南岛铁路网
• 台湾铁路网

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

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

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

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

边的权:在一个图中,每条边都可以标上具有某种含义的数值,该数值称为该边的权值.
带权图/网:边上带有权值的图称为带权图,也称网.

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

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

若无向图的顶点数|V|=n,则 $|E|\in[0,C_n^2]=[0,\dfrac{n(n-1)}{2}]$

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

若有向图的顶点数|V|=n,则 $|E|\in[0,2C_n^2]=[0,n(n-1)]$

边很少的图称为稀疏图,反之称为稠密图.

稀疏图和稠密图之间没有绝对的界限,一般来说|E|<|V|log|V| 时,可以将G视为稀疏图.

树:不存在回路,且连通的无向图
n个顶点的树,则必有n-1条边

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

有向树:一个顶点的入度为0,其余顶点的入度均为1的有向图,称为有向树

图的存储

临接矩阵

无向图中，若两个顶点之间邻接，则为1，若两个顶点之间不邻接，则为0.

#define MaxVertexNum 100  // 顶点数目的最大值
typedef struct {
  char Vex[MaxVertexNum]; // 顶点表（顶点中可以存更复杂的信息）
  int Edge[MaxVertexNum] [MaxVertexNum]; // 邻接矩阵，边表（可以用bool型）
  int vexnum, arcnum; // 图当前顶点数和边数/弧数
} MGraph;

结点数为n的图G=(V, E) 的邻接矩阵A是n×n的。将G的顶点编号为 $v_1,v_2,\cdots,v_n$，则 $A[i][j]=\begin{cases} 1, &\text{若}(v_i,v_j)\text{或}<v_i,v_j>\text{是}E(G)\text{中的边}\
0, &\text{若}(v_i,v_j)\text{或}<v_i,v_j>\text{不是}E(G)\text{中的边}\
\end{cases}$

对于无向图的度，只要检查第i行或者第i列非零元素的个数即可
对于有向图的度，出度为第i行非零元素个数，入度为第i列非零元素个数，第i个节点的度为第i行和第i列的非零元素个数之和

存储带权图
将1换成对应边的权值，0换成无穷

#define MaxVertexNum 100    // 顶点数目的最大值
#define INFINITY 最大的int值 // 宏定义常量“无穷”
typedef char VertexType;    // 顶点的数据结构
typedef int EdgeType;       // 带权图中边上权值的数据类型
typedef struct {
  VertexType Vex[MaxVertexNum]; // 顶点 
  EdgeType Edge[MaxVertexNum] [MaxVertexNum]; // 边的权
  int vexnum. arcnum; // 图的当前定点数和弧数
} MGraph;

邻接矩阵法存储带权图可以用0或者无穷来表示两个点之间不存在边

邻接矩阵的空间复杂度为O(n^2)，适合用于存储稠密图
易知，无向图的邻接矩阵是对称矩阵，可以压缩存储，只存储上三角区或下三角区（之前有说错如何存储压缩矩阵，简单图中不能直接和自己相连，因此主对角线上的元素都为空）

邻接矩阵的性质
设无向图的邻接矩阵为 $\boldsymbol{A}$(矩阵元素为0/1)，则 $\boldsymbol{A}^n$ 的元素 $\boldsymbol{A}^n[i][j]$ 等于由顶点i到顶点j的长度为n的路径的数目

邻接表

顶点

typedef struct VNode{
  VertexType data; // 顶点信息
  ArcNode *first;  // 第一条边/弧
} VNode, AdjList [MaxVertexNum];

用邻接表存储的图

typedef struct {
  AdjList vertices;
  int vexnum, arcnum; // 记录了有多少个顶点，多少条弧
}ALGraph;

边/弧

typedef struct ArcNode {
  int adjvex; // 当前这条边/弧指向哪个结点
  struct ArcNode *next;// 指向下一条弧的指针
  // InfoType info; // 边权值
}ArcNode;

邻接表法就是我把所有的结点列出来，比如有ABCD四个结点

无向图使用邻接表法，会产生数据冗余，比如A到B有边，那么会有A到B和B到A的边，等于一条边记了两次，空间复杂度更高

有向图的空间复杂度更低

对于无向图来说，获得某个结点的度，只需要遍历该节点的边
对于有向图来说，度=入度+出度，找出度很简单，遍历该节点即可，但是要获得入度则需要遍历所有的边，时间复杂度比较高

图的邻接表表示并不唯一，选*first比较随意，邻接矩阵法表示法唯一

十字链表法

用于存储有向图

用一个数组存储顶点结点

顶点结点存储

• 数据域data
• 该顶点作为弧头的第一条弧firstin
• 该顶点作为弧尾的第一条弧firstout

弧结点存储

• 弧尾顶点编号tailvex
• 弧头顶点编号headvex
• 权值info(可能会没有)
• 弧头相同的下一条弧hlink
• 弧尾相同的下一条弧tlink

这边的编号就是对应数组中顶点的索引，就是一个数字

空间复杂度为O(|V|+|E|)，只需要弧的数量和结点的数量即可
相对于邻接矩阵法的空间复杂度为O(|V|^2) 小很多

邻接多重表

用于存储无向图

邻接表和邻接矩阵存储无向图，删除边和结点会比较麻烦，因此可以使用邻接多重表

与十字链表法类似的，用一个数组存储顶点结点

顶点结点存储

• 数据域
• 与该顶点相连的第一条边

边结点存储

• 边的两个顶点编号i，j
• 权值info(可以没有)
• 依附于顶点i的下一条边
• 依附于顶点j的下一条边

与十字链表法类似，边结点存储的顶点编号就是顶点结点在数组中的索引

基本操作

因为基本操作和存储结构密不可分，所以我们这边以邻接矩阵和邻接表作为基本存储结构

基本操作：

• Adjacent(G,x,y):判断图G是否存在边<x,y>或<y,x>
• Neighhbors(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

Adjacent(G,x,y):判断图G是否存在边<x,y>或(x,y)

• 无向图：
  • 邻接矩阵，时间复杂度O(1)
  • 邻接表，最坏时间复杂度O(|V|)
• 有向图方法和无向图类似

Neighbors(G,x):列出图G中与结点x邻接的边

• 无向图
  • 邻接矩阵，只需要遍历对应的行或者列，时间复杂度为O(|V|)
  • 邻接表，遍历对应的结点最好为O(1)，最坏为O(|V|)
• 有向图
  • 邻接矩阵，遍历对应的行或列可以得到对应的入边和出边
  • 邻接表，出边只要遍历对应结点即可，但是如果是入边则需要遍历整个邻接表

InsertVertex(G,x):在图G中插入顶点x

• 无向图
  • 邻接矩阵，将对应的行和列初始化为0，写入对应的数据O(1)
  • 邻接表，将*first初始化为空，新增结点信息O(1)
• 有向图类似

DeleteVertex(G,x):从图G中删除顶点x

• 无向图
  • 邻接矩阵，一种是删除对应的行和列，然后移动其余的元素，拼接起来，另一种是将对应的行和列全部置为0，在结构体中增加一个bool类型，表示是否顶点是否是一个空顶点O(V)
  • 邻接表，删除结点，以及其他元素和结点相连的边O(1)~O(|E|)
• 有向图
  • 邻接矩阵，和无向图一样
  • 邻接表，删除出边，删除结点即可，删除入边，需要遍历整个表删除入边

AddEdge(G,x,y):若无向边(x,y)或有向边<x,y>不存在，则向图G中添加该边

• 无向图
  • 邻接矩阵，O(1)
  • 邻接表，对应两个结点进行头插法，O(1)
• 有向图基本一致O(1)

FirstNeighbor(G,x):求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1

• 无向图
  • 邻接矩阵，对对应的行进行遍历
  • 邻接表，对对应的结点进行遍历
• 有向图
  • 邻接矩阵，出边扫描对应的行，找入边扫描对应的列
  • 邻接表，找出边O(1)，找入边O(1)~O(|E|)

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)
• 深度优先遍历(DFS)

广度优先遍历

树的广度优先遍历和层序遍历差不多

树是特殊的图，因此图的广度优先和树的广度优先类似

图和树的区别在于，树不可能有回路，图可能有回路，因此我们可以通过增加一种数据来表示我们是否已经经过了这个点

广度优先遍历（Breadth-First-Search,BFS）要点：

1. 找到一个与一个顶点相邻的所有顶点
2. 标记哪些顶点被访问过
3. 需要一个辅助队列

// 标记访问数组
bool visited [MAX_VERTEX_NUM]; 

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

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

这个算法有一个问题，如果是非连通图，则无法遍历完所有结点，所以可以进行一定的改进

// 对图G 进项广度优先遍历
void BFSTraverse(Graph G){
  for (i=0;i<G.vexnum;i++){
    // 初始化标记数组
    visited[i] = FALSE;
  }
  InitQueue(Q);
  for(i=0;i<G.vexnum;i++){
    if(!visited[i])
      BFS(G,i);
  }
}

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

这边其实还是有一些小问题，但是无伤大雅，比如这个队列Q应该定义为全局变量

广度优先生成树
连通图根据广度优先遍历的过程得到的，保留广度优先遍历时经过的边，即可得到一个广度优先生成树，如果是非连通图则可得到广度优先生成森林

邻接表的表达方式不唯一，因此通过这种方法得到的广度优先生成树不唯一

深度优先遍历

树也有深度优先遍历：先根遍历和后根遍历，图的深度优先算法与树的先根遍历更相似

由于树的特性，访问到的结点一定是之前没有访问过的，因此和广度优先算法一样，也是需要一个visited数组来存储是否有被访问过

bool visited[MAX_VERTEX_NUM]; // 访问标记数组

void DFS(Graph G, int v) {
  // 访问顶点 v
  visit(v);
  // 设已访问标记
  visited[v] = TRUE;
  for (w = FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
    // w 为u的尚未访问的邻接顶点
    if(!visited[w]){
      DFS(G,w);
    }
  }
}

同样的，如果是非连通图，还需要加上

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);
  }
}

与广度优先遍历相同的，如果存储方式是邻接矩阵的话，遍历序列是唯一的，如果存储方式是邻接表的话，遍历序列是不唯一的

深度优先生成树和广度优先生成树类似，深度优先生成森林和广度优先生成森林类似

调用深度优先遍历的次数=连通分量的个数

最小生成树

连通图的生成树包含图中全部顶点的一个极小连通子图。

最小生成树（最小代价树）
对于一个带权连通无向图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算法（无权图）
  • Dijkstra算法（带权图、无权图）
• 各顶点间的最短路径
  • Floyd算法（带权图、无权图）

无权图其实可以看做一种特殊的带权图，只是每条边的权值都为1，或者看成相同的权值

求顶点 u 到其他顶点的最短路径

void BFS_MIN_Distance(Graph G, int u){
  // d[i] 表示u到i结点的最短路径
  for(int i=0;i<G.vexnum; i++) {
    d[i] = ∞;//初始化路径长度，无穷只是表意，但是实际上不可以存无穷，实际可以写-1
    path[i] = -1;//最短路径从哪个顶点过来
  }
  d[u]=0;
  visited[u] = FALSE;
  EnQueue(Q, u);
  while(!isEmpty(Q)) {
    // 队头元素 u 出队
    DeQueue(Q, u);
    for (w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w)){
      if(!visited[w]){
        d[w] =d[u]+1;
        path[w] = u;
        visited[w] = TRUE;
        EnQueue(Q,w);
      }
    }
  }
}

Dijkstra算法

BFS算法的局限性，是默认权相同
带权路径长度：当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度，简称路径长度

声明：Dijkstra算法不适用于负权图，后面再举例，现在我们先假设都是正权图

算法：

• 找到起始点v_0
• 初始化数组
  • final数组：标记各个顶点是否已经找到最短路径
  • dist数组：最短路径长度
  • path数组：路径上的前驱
• 找到final中为false，并且dist最小的点，假设为v_1
• 更新final，dist，path
• 重复更新，直到final所有都为true

初始化final：v_0对应的final为true，其他为false
初始化dist：从v_0直接到各个点的距离，如果没有直接相连，那么距离为无穷
初始化path：与v_0直接相连的点path记为v_0的索引,v_0对应的path值为0

更新final：v_1的final设为true
更新dist、path：与v_1直接相连，且final为false的点，比较这些点的dict与（v_1到这些点的距离+v_1对应的dict）的大小，如果后者更小，那么将这些连接的点的dict更新成小的，并且将这些点的path更新成v_1的索引，如果后者更大，就不变

每次更新都会将final中的一个点转化为true，因此只需要更新n-1次，就能获得指定点到所有点的最短距离

整个算法的时间复杂度为 O(n^2)

Dijkstra算法不适用于负权图，例子如下

graph LR
A((A)) --10--> B((B))
B -- -5--> C((C))
A --7--> C

假设从A出发，那么

我们发现dist最小的值为7，对应C，因此进行更新

因为C不能到B，因此继续选择final为false，dist最小的B，再次更新

但是实际上，A到C的最短带权路径长度为5,这时候Dijkstra算法失效

Floyd算法

用于求解每一对顶点之间的最短路径
使用动态规划思想，将问题的求解分为多个阶段

初始化矩阵A，和path矩阵，初始化时，假设不能再任何点中转，计算两个点之间的距离，A是路径长度，如果两个点之间不能直接相连，那么路径长度为无穷，path存两个点之间的中转点，一开始全是-1

// 考虑以V_k作为中转点
// 把每个点加入中转点可选项
for (int k=0; k<n; k++) {
  接下来遍历整个矩阵
  for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
      if (A[i] [j]>A[i][k]+A[k][k]){
        A[i][j] = A[i][k]+A[k][j];
        path[i][j] = k;
      }
    }
  }
}

时间复杂度为 O(n^3)，空间复杂度为 O(n^2)

Floyd算法可以解决一些带负权值的图，但是无法解决带有“负权回路”的图这种图可能没有最短路径

graph LR
A((A)) -- -9--> B((B))
B --3--> C((C))
C --5--> A

有向无环图(DAG)

有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG(Directed Acyclic Graph)

在树中有时候会出现完全相同的部分，为了节省空间，我们可以只存一份，两个结点都指向这一份，形成有向无环图，因为结点永远向下指(可能说起来不严谨)，因此永远都不会形成环

例如：
表达式 (x+y)*((x+y)/x)，用树表达为

graph TD;
A((*)) --> B((+));
A --> C((/));
B --> X((x));
B --> Y((y));
C --> D((+));
C --> X2((x));
D --> X3((x));
D --> Y2((y));

我们会发现其中有一些子树是完全一样的，我们可以只保留一份，比如

graph TD;
A((*)) --> B((+));
A --> C((/));
B --> X((x));
B --> Y((y));
C --> B;
C --> X2((x));

其实仔细观察，会发现单独的两个x也是重复的结点，因此我们可以再次改造

graph TD;
A((*)) --> B((+));
A --> C((/));
B --> X((x));
B --> Y((y));
C --> B;
C --> X;

这样就得到了最后的有向无环图

拓扑排序

AOV网(Activity On Vertex Network,用顶点表示活动的网)
用DAG图(有向无环图)表示一个工程。顶点表示活动，有向边<V_i, V_j> 表示活动 V_i 必须先于活动 V_j 进行

拓扑排序的定义：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，成为该图的一个拓扑排序：

1. 每个顶点出现且只出现一次
2. 若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径

拓扑排序的实现：

• 从AOV网中选择一个没有前驱(入度为0)的顶点并输出
• 从网中删除该顶点和所有以它为起点的有向边
• 重复上面两个步骤知道当前AOV网为空或当前网中不存在无前驱的顶点为止

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

逆拓扑排序
拓扑排序是删除入度为0的顶点，逆拓扑排序是删除出度为0的顶点，用邻接表实现会比较麻烦，可以考虑逆邻接表或者邻接矩阵

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

// 对图G进行深度优先遍历
void DFSTraverse (Graph G) {
  int v;
  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
  visited[v] = TRUE;
  for (w= FisrtNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w))
    if (!visited[w])
      // w 为 u 尚未访问的邻接顶点
      DFS(G, w);
  
  print(v); // 输出顶点，这里有点不严谨，只是为了表意
}

推出调用栈之前才会输出v，这里事实上没有对回路进行判断

关键路径

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)，表示在不增加完成整个工程所需总时间的情况下，活动a_i可以拖延的时间

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

自然地，如果关键活动耗时增加，则震哥哥工程的工期将增长
缩短关键活动的时间，可以缩短整个工程的工期
当缩短到一定程度时，关键活动可能会变成非关键活动

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