声明：本文章主要用于408考研学习，梳理了考试中的重点及易错点，若有错误敬请指出。
参考书籍：《数据结构(第二版)》严蔚敏、李冬梅、吴伟民，《数据结构考研复习指导》王道计算机教育
参考资料：图的定义

一、图的定义

1. 边集E(G)可以为空集，但是图不能为空图，图中必须至少有1个顶点。
2. 无向完全图有 $\frac{n(n-1)}{2}$ 条边，有向完全图有 n(n-1) 条边。
3. 有向图：顶点的度 = 出度 + 入度（有向图的全部顶点的入度之和与出度之和相等，并且等于边数。因为每条有向边都有一个起点和终点。）
4. 图（不管有向图还是无向图）的全部顶点之和等于边数的 2 倍。
5. 若一个图有 n 个顶点，且有大于 n-1 条边，则此图一定有环。
6. 若一个图有 n 个顶点，且有小于 n-1 条边，则此图一定是非联通图。

二、图的存储

2.1 邻接矩阵（稠密图）

1.邻接矩阵的表示
有向图和无向图的邻接矩阵表，用0表示边不存在；

网（带权图）用 ∞ 表示边不存在，对角线元素也常用 0 表示。

2.其他考点
1） 图G的邻接矩阵为 A，Aⁿ 的元素 Aⁿ_ij 表示由顶点 i 到顶点 j 的长度为 n 的路径的数目。
2）无向图的邻接矩阵对称且唯一，可以压缩存储。

3.优缺点
【优点】1）便于判断两个顶点之间是否有边；2）便于计算各个顶点的度。

对于无向图，邻接矩阵第 i 行元素之和就是顶点 v_i 的度。
对于有向图，第 i 行元素之和就是顶点 v_i 的出度，第 i 列元素之和就是顶点 v_i 的入度。

【缺点】1）不便于增加和删除顶点；2）空间复杂度高；3）不便于统计边的数目。

不论是有向图的存储，还是无向图压缩存储，空间复杂度都是 O(n²)
统计边的数目需要遍历邻接矩阵，时间复杂度为 O(n²)

2.2 邻接表（稀疏图）

1.易错点：
1）一个图的邻接矩阵唯一，但邻接表不唯一。
2）无向图的邻接表表示中，每条边都被存储了 2 次（1条边的存储和增删都要操作2次，而且删需要遍历 2 个边表）。

【补充——邻接表的数据结构】
邻接表的组成包括 表头结点表 和 边表。所有表头结点以顺序结构的形式存储。表头节点表的表头结点包括数据域（存储顶点的名称或其他信息）和链域（指向第一个邻接点）；边表的边节点包括邻接点域（指示与顶点 v_i 相邻的点在图中的位置）、数据域（储存权值）、链域（指向 v_i 的下一个邻接点）。

图2.2.1- 邻接表的数据结构

现给出有向图G₁和G₂

图2.2.2- 有向图和无向图

对应的邻接表、逆邻接表结构如图：

图2.2.3- 邻接表和逆邻接表

2.优缺点
【优点】1）便于增加和删除顶点；2）便于统计边的数目；3）空间效率高。

1.对于无向图，增加和删除节点，都需要对一条边操作两次
2.统计边的数目，只需按顶点表顺序查找所有边表，时间复杂度为O(n + e)
3.无向图要存储 n 个顶点表节点 + 2e 个边表节点；而有向图则要存储 n 个顶点表节点 + e 个边表节点
4.邻接表或逆邻接表表示的空间复杂度为O(n + e)，适合表示稀疏图。对于稠密图，考虑到邻接表中要附加链域，因此常采取邻接矩阵表示法

【缺点】1）不便于判断顶点之间是否有边；2）不便于计算有向图各个顶点的度。

1.对于无向图，在邻接表表示中顶点 v_i 的度是第 i 个边表中的节点个数。
2.在有向图的邻接表中，第 i 个边表上的节点个数是顶点 v_i 的出度，但求 v_i 的入度困难（需遍历各顶点的边表）。若有向图采用逆邻接表表示，则求入度容易，求出度困难。
3.要判定 v_i 和 v_j 之间是否有边，就需查找第 i 个边表，最坏情况下时间复杂度为O(n）

2.3 十字链表法（有向图）

参考文章：数据结构——关于图的存储中十字链表和邻接多重表的理解和思考

1.十字链表法，有向图的一种链式存储结构，可看作有向图邻接表和逆邻接表结合起来得到的一种链表。
2.弧头相同的弧在同一链表上，弧尾相同的弧也在同一链表上。
3.创建十字链表和邻接表法的时间复杂度相同，都是 O(n+e)
4.图的十字链表表示并不唯一，但一个十字链表表示唯一确定一个图。

【补充——十字链表的数据结构】
在十字链表中，对应于有向图中每一条弧有一个节点，对应于每个顶点也有一个节点。
▶ 在弧节点中有5个域：其中尾域（tailvex）和头域（headvex）分别指示弧尾和弧头这两个顶点在图中的位置，链域hlink指向弧头相同的下一条弧，而链域tlink指向弧尾相同的下一条弧，info域指向该弧的相关信息。弧头相同的弧在同一链表上，弧尾相同的弧也在同一链表上。
▶ 在头节点（顶点节点）有3个域：其中data存储和顶点相关的信息，如顶点的名称等；firstin和firstout为两个链域，分别指向以该顶点为弧头或弧尾的第一个弧节点。

图2.3.1- 弧节点和顶点节点的结构

图2.3.2给出了一个有向图的十字链表。
绿色的链域是 v₁ 节点的入度，沿着绿色链表可以找到所有指向 v₁ 节点的节点位置；蓝色的链域则是 v₁ 节点的出度，沿着蓝色链表可以找到所有 v₁ 节点所指向的节点位置。
可以看到蓝色链表中的 tailvex 保存的都是 0 ，表明它们都是以 0 位置的 v₁ 作为弧尾（即 v₁ 的出度）；而绿色链表中的 headvex 保存的也都是 0 ，表明它们都是以 0 位置的 v₁ 作为弧头（即 v₁ 的入度）。

图2.3.2- 有向图的十字链表

2.4 邻接多重表（无向图）

1.邻接多重表是无向图的一种链式存储结构。
2.在某些图的应用问题中需要对边进行某种操作，如对已被搜索过的边进行标记或删除一条边等，此时需要找到表示同一条边的两个节点。因此，在进行这一类操作（对边操作）的无向图的问题中采用邻接多重表作为存储结构更合适。

【补充——邻接多重表数据结构】
邻接多重表的结构和十字链表类似。对无向图而言，其邻接多重表和邻接表的差别，仅仅在于同一条边在邻接表中用两个节点表示，而在邻接多重表中只用一个节点表示。因此，除了在边节点中增加一个标志域外，邻接多重表所需的存储量和邻接表所需的相同。
在邻接多重表中，每条边用一个节点表示，每个顶点也用一个节点表示。
▶ 边节点由6个域组成：其中，mark为标志域，可用以标记该条边是否被搜索过；ivex和jvex为该边依附的两个顶点在图中的位置；ilink指向下一条依附于顶点ivex的边；jlink指向下一条依附于顶点jvex的边，info为指向和边相关的各种信息的指针。
▶ 顶点节点由2个域组成：data存储和该顶点相关的信息，firstedge指示第一条依附于该顶点的边。

图2.4.1- 弧节点和顶点节点的结构

图2.2.2中无向图G₂对应的邻接多重表如下：

图2.4.2- 无向图的多重邻接表

三、图的遍历（⭐重点）

1. 为了避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点。因此，BFS和DFS都必须：设一个辅助数组 visited[n] ，其初始值置为 “false” 或者0，一旦访问了顶点 v_i，便置 visited[i] 为 “true” 或者1。
2. 遍历图的过程实质上是通过边找邻接点的过程，因此，广度优先搜索遍历（BFS）和深度优先搜索遍历（DFS）的时间复杂度相同。即当用邻接矩阵存储时，时间复杂度为 $O(n^2)$ ；用邻接表存储时，时间复杂度为 $O(n+e)$。两种遍历方法的 不同之处仅仅在于对顶点访问的顺序不同。
3. 基于邻接矩阵得到的 DFS 和 BFS 序列是唯一的，但基于邻接表得到的 DFS 和 BFS 序列可能不唯一。
4. 无向图调用 DFS 或 BFS 的次数 = 图中联通分量数

3.1 深度优先搜索（DFS）

深度优先搜索（Depth First Search，DFS）遍历类似于树的先序遍历，是树的先序遍历的推广。深度优先搜索遍历连通图是一个递归的过程。

【遍历过程】
对于一个连通图，深度优先搜索遍历的过程如下。

1. 从图中某个顶点 v 出发，访问 v 。
2. 找出刚访问过的顶点的第一个未被访问的邻接点，访问该顶点。以该顶点为新顶点，重复此步骤，直至刚访问过的顶点没有未被访问的邻接点为止。
3. 返回前一个访问过的且仍有未被访问的邻接点的顶点，找出该顶点的下一个未被访问的邻接点，访问该顶点。
4. 重复步骤 2 和步骤 3 ，直至图中所有顶点都被访问过，搜索结束。

对于非连通图，上述遍历过程执行之后，图中一定还有顶点未被访问，需要从图中另选一个未被访问的顶点作为起始点，重复上述深度优先搜索过程，直到图中所有顶点均被访问过为止。

算法如下（包含邻接表法和邻接矩阵法的DFS实现）

bool visited[MVNum];   //访问标志数组，其初值为“false”
void DFSTraverse(Graph G){  //可以改成 AMGraph或 ALGraph
// 对非连通图进行深度遍历
	for(v=0;v<G.vexnum;++v)	visited[v]=false;  // 访问标志数组初始化
	for(v=0;v<G.vexnum;++v)   // 依次检查所有顶点
		if(!visited[v]) DFS(G,v);  // 对新的连通分量启动一次新的 DFS
		// DFS()相应改成 DFS_AM()或 DFS_AL()
}

void DFS_AM(AMGraph G,int v){
// 图 G为邻接矩阵类型，从第 v个顶点出发深度有点搜索遍历图 G
	printf("%d",v); //访问顶点v
	visited[v]=true;  //标记v为已访问
	for(w=0,w<G.vexnum;w++){   //依次检查邻接矩阵 v所在的行
		if((G.arcs[v][w]!=0) && (!visited[w]))
		//G.arcs[v][w]!=0表示 w是 v的邻接点，若 w未访问，则递归调用 DFS_AM()
			DFS_AM(G,w);
	}
}

void DFS_AL(ALGraph G,int v){
//图 G为邻接表类型，从第 v个顶点出发深度优先搜索遍历图G
	printf("%d",v);    //访问第 v个顶点
	visited[v]=true;   //置访问标志数组相应分量值为 true 
	p=G.vertices[v].firstarc;    // p指向 v的边链表的第一个边节点(邻接点)
	while(p!=NULL){       // 遍历 v的邻接链表
		w=p->adjvex;        //取出一个邻接点 w
		if(!visited[w])         //如果 w未被访问过
			DFS_AL(G,w);        //则递归访问 w
		p=p->nextarc;　　   //p指向下一个边节点(邻接点)
	}
}

【时间复杂度】
邻接矩阵法：用二维数组存边，DFS 时对每个顶点逐行扫描，时间复杂度 O(n²)。
邻接表法：用链表存边，DFS 时逐顶点扫描边表，时间复杂度 O(n + e)。

【注】在遍历图时，对图中每个顶点至多调用一次DFS()函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。当用邻接矩阵表示图时，查找每个顶点的邻接点的时间复杂度为O(n²)，其中 n 为图中顶点数。而当以邻接表作为图的存储结构时，查找邻接点的时间复杂度为O(e)，其中 e 为图中边数。由此，当以邻接表作为存储结构时，深度优先搜索遍历图的时间复杂度为O(n + e)。

3.2 广度优先搜索（BFS）

BFS的其他用途：求非带权图的单源最短路径

广度优先搜索遍历类似于树的按层次遍历的过程，算法实现时需引入队列保存已被访问过的顶点。

【遍历过程】
广度优先搜索遍历的过程如下。
（1）从图中某个顶点v出发，访问v。
（2）依次访问v的各个未曾访问过的邻接点。
（3）分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问。重复步骤（3），直至图中所有已被访问的顶点的邻接点都被访问到。

算法如下（包括邻接表法和邻接矩阵的BFS实现）

void BFSTraverse(Graph G) {  //相应改成 ALGraph或 AMGraph
//同 DFS的连通图遍历算法，只不过调用DFS()改成了调用BFS()
    for (int v=0; v<G.vexnum; v++) visited2[v]=false;
    for (int v=0; v<G.vexnum; v++){
        if (!visited[v])
            BFS(G,v); //BFS相应改成BFS_AL()或BFS_AM
    }
}

void BFS_AM(AMGraph G,int v){
// 邻接矩阵法实现BFS
	printf("%d",v);visited[v]=true; //访问第v个顶点，并置访问标志数组相应分量值为true
	InitQueue(Q);　　　　　 //辅助队列 Q初始化，置空
	Enqueue(Q,v);　　      //v入队
	while(!QueueEmpty(Q)){   //只要队列不空，就不断取出队头顶点 u
		DeQueue(Q,u);　　　　 //队头元素出队并置为 u
		for (int w=0;w<G.vexnum;w++){   //扫描 u的邻居（邻接点）
			if((G.arcs[u][w]!=0) && (!visited[w]))  //u和 w若有边（是邻居）,且 w未被访问过
				printf("%d",w);visited[v]=ture;  //则访问邻居，并标记为已访问
				EnQueue(Q,w);   //将邻居入队
		}
	}
}

void BFS_AL(ALGraph G,int v){
//邻接表法实现BFS
	printf("%d",v);visited[v]=true; //访问第v个顶点，并置访问标志数组相应分量值为true
	InitQueue(Q);　　　　　 //辅助队列 Q初始化，置空
	Enqueue(Q,v);　　      //v入队
	while(!QueueEmpty(Q)){
		DeQueue(Q,u);
		ArcNode *p=G.vertices[u].first;
		while (!p){
			int w=p->adjvex;  //w指向下一个邻接点（邻居）
			if(!visited[w])   //若邻居未被访问，则访问该邻居并将其入队
				printf("%d",w);visited[v]=ture;
				EnQueue(Q,w);
		}
		p=p->next;
	}
}

四、图的应用

4.1 最小生成树

定义：各边代价之和最小的树，常见应用场景为以最低的代价联通 n 个城市。
易错点：最小生成树一定包含至少一条权值最小边。但注意，并不是所有小边都在最小生成树里面（有些边的权值是可能超过未选边权值的，如下表）

图G	最小生成树

Prim算法

【算法思想】 每次总是选出一个离生成树距离最小的点去加入生成树，最后实现最小生成树。

图4.1所示为连通网G5从v₁开始构造最小生成树的过程。可以看出，普里姆算法逐步增加U中的顶点，可称为 “加点法” 。

图4.1-普里姆算法构造最小生成树的过程

【算法分析】 Prim 算法的 时间复杂度为O(n²)，与网中的边数无关，因此适用于求稠密网的最小生成树。

Kruskal算法

【算法思想】 每次选择权值最小的边，确保不会形成回路，直到所有顶点都被连接。

例如，对图4.1（a）所示的连通网G₅，图4.2所示为依照Kruskal算法构造最小生成树的过程。权值分别为1、2、3、4的4条边由于满足上述条件，因此先后被加入T中；权值为 5 的两条边(v₁, v₄)和(v₃, v₄)被舍去。因为它们依附的两顶点在同一连通分量上，它们若加入T中，则会使T中产生回路，而下一条权值（ = 5）最小的边(v₂, v₃)连结两个连通分量，则可加入T。由此，构造成一棵最小生成树。

图4.2-克鲁斯卡尔算法构造最小生成树的过程

【算法分析】 对于包含 e 条边的网，Kruskal 算法的时间复杂度为 O(elog₂e)，与网中的边数有关，更适合求稀疏网的最小生成树。

4.2 最短路径

BFS

BFS 可求 非带权图 的单源最短路径。
Dijsktra 可求 图（有权无权都可） 的单源最短路径，但图中 权值不能为负值。
Floyd 可求 图（有权or无权、负权or正权均可）中每队顶点的最短路径，但图中 不能有带负权值的回路。

Dijsktra 单源最短路径（⭐必考重点）

参考文章：Dijkstra算法详解（C++实现，附带示例）
Dijsktra 算法不适用于边上带有负权值的情况。

（1）迪杰斯特拉算法的求解过程
对于网 N = (V, E)，将N中的顶点分成两组。

▶ 第一组 S：已求出的最短路径的终点集合（初始时只包含源点 v₀）。
▶ 第二组 D = V − S：尚未求出的最短路径的顶点集合（初始时为V − { v₀ }）。

算法将按各顶点与 v₀ 间最短路径长度递增的次序，逐个将集合V−S中的顶点加入集合S中去。在这个过程中，总保持从 v₀ 到集合 S 中各顶点的路径长度始终不大于到集合 V − S 中各顶点的路径长度。

（2）迪杰斯特拉算法的实现

假设用带权的邻接矩阵arcs来表示带权有向网 G，源点为 v₀，G.arcs[i][j] 表示弧<v_i, v_j>上的权值。若<v_i, v_j>不存在，则置 G.arcs[i][j] 为∞。

【辅助数据结构】：
① 一维数组 S[i]：记录从源点 v₀ 到终点 v_i 是否已被确定最短路径长度，true表示确定，false表示尚未确定。
② 一维数组 Path[i]：记录从源点 v₀ 到终点 v_i 的当前最短路径上 v_i 的直接前驱顶点序号。其初值为：如果从 v₀ 到 v_i 有弧，则 Path [i] 为 v₀，否则为−1。
③ 一维数组 D[i]：记录从源点 v₀ 到终点 v_i 的当前最短路径长度。其初值为：如果从 v₀ 到 v_i 有弧，则 D[i] 为弧上的权值，否则为∞。

最短路径必为(v₀, v_k)，其满足以下条件：

D[k] = min{D[i]|vi∈V − S}

【算法具体过程】
1）求得顶点 v_k 的最短路径后，将其加入第一组顶点集 S 中。

2）更新第二组剩余顶点的最短路径长度。每当加入一个新的顶点到顶点集S，对第二组剩余的各个顶点而言，多了一个“中转”顶点，从而多了一个“中转”路径，所以要对第二组剩余的各个顶点的最短路径长度进行更新。

【更新过程】 原来 v₀ 到 v_i 的最短路径长度为 D[i]，加入 v_k 之后，以 v_k 作为中间顶点的“中转”路径长度为 D[k] + G.arcs[k][i]，若 D[k] + G.arcs[k][i]<D[i]，则用 D[k] + G.arcs[k][i] 取代 D[i]。

3）更新后，再选择数组 D 中值最小的顶点加入第一组顶点集 S 中，如此进行下去，直到图中所有顶点都加入第一组顶点集 S 中为止。

void ShortestPath_DIJ(AMGraph G, int v0)
{//用Dijkstra算法求有向网的v0顶点到其余顶点的最短路径
	n=G.vexnum;　　　　　　　　　　 //n为G中顶点的个数
	for(v=0;v<n;++v) //n个顶点依次初始化
	{
		S[v]=false;
		// S[v] 表示“是否已确定最短路径”的集合标记，初始都是 false
		
		D[v]=G.arcs[v0][v];
		// D[v] 表示“从 v0 到 v 的当前最短距离”，初始直接用邻接矩阵里的权值
		
		if(D[v]<MaxInt) Path[v]=v0; 
		// 如果 v0 到 v 有边，则记录 v 的前驱是 v0
		
		else Path[v]=-1;
		// 如果 v0 到 v 没有直接边，则前驱记为 -1（不可达）
	} //for 
	
	S[v0]=true;
	// v0 自己到自己的最短路径肯定已知，标记进入 S 集合 
	
	D[v0]=0;
	//源点v0到自身的距离为0 
	
 /*----------------------------------------------------------
      初始化结束
      - S 集合存放“已确定最短路径”的顶点
      - D 数组存放 v0 到各顶点的最短距离估计值
      - Path 记录每个顶点的前驱，用于输出路径
      接下来主循环：每次把一个新的顶点加入 S
 -----------------------------------------------------------*/
	for(i=1;i<n;++i) // 一共要选择 n-1 个顶点加入 S
	{
		min=MaxInt;
		for(w=0;w<n;++w) 
			if(!S[w]&&D[w]<min)
				{v=w;min=D[w];}　　　　 //选择一条当前的最短路径，终点为v 
		// 在所有未加入 S 的顶点中，找到距离 D[w] 最小的顶点 v
     // 这意味着：D[v] 已经是最短路径值，可以确定

		S[v]=true;
		// 将 v 加入 S 集合，表示 v 的最短路径已确定
		
		for(w=0;w<n;++w)　　　　 //更新从v0出发到集合V − S上所有顶点的最短路径长度
			if(!S[w]&&(D[v]+G.arcs[v][w]<D[w]))
			{
				D[w]=D[v]+G.arcs[v][w]; //更新D[w] 
				Path[w]=v;　　　　　　　 //更改w的前驱为v 
			} //if 
　　　  // 尝试用 v 作为“中间点”去更新 v0 到 w 的最短距离
       // 如果经过 v 可以让路径更短，则更新 D[w]，并修改 w 的前驱为 v
      
	} //for
}

【时间复杂度分析】 主循环共进行 n−1 次，每次执行的时间是 O(n)，所以算法的 时间复杂度是O(n²)。如果用带权的邻接表作为有向图的存储结构，则虽然修改 D 的时间可以减少，但由于在 D 中选择最小分量的时间不变，所以时间复杂度仍为O(n²)。

Floyd 每对顶点间最短路径（❄️冷门考点）

参考视频：数据结构1800题型-Floyd算法求最短路径
参考文章：弗洛伊德（Floyd）算法求图的最短路径
Floyd 算法也叫 “插点法” 。

适用于带负权值的边，但不允许有包含带负权值的边组成的回路；也适用于带权无向图。

求每对顶点间的最短路径，不论用 Floyd 还是 Dijsktra 算法，时间复杂度都为 O(n³)

【Floyd算法过程变化示例】

图4.2-Floyd 算法示例

4.3 有向无环图 DAG

DAG描述表达式

参考文章：有向无环图-描述表达式
在有向无环图中不可能出现重复的操作数顶点

拓扑排序（⭐热门考点）

参考文章：拓扑排序算法实现、判断有向图是否有环的方法
考察形式：考选择、2024年考了拓扑排序的代码实现

1）拓扑排序是 针对有向无环图 的顶点的一种排序；
2）AOV网中不存在环；
3）❗DFS、拓扑排序可以判断有向图是否有环（而且拓扑排序是可以用DFS实现的）；
4）❗拓扑序唯一 ≠ 图唯一（无论是否带权）。唯一拓扑序只能说明图的每个顶点之间都有确定的相对顺序，但边的具体集合、权值都不能由拓扑序唯一确定。

【知识点补充】
AOV网：用顶点表示活动，用弧表示活动间的优先关系的有向图称为以顶点表示活动的网。
在AOV-网中，不应该出现有向环，即任何活动不能作为以自己作为自己的前驱或后继。若设计出这样的流程图，工程便无法进行。因此，对给定的AOV-网应首先判定网中是否存在环。检测AOV网中是否有环的办法是，对有向图的顶点进行拓扑排序，若网中所有顶点都在它的拓扑有序序列中，则该AOV-网中必定不存在环。

拓扑排序满足：
1）每个顶点出现且只出现一次。
2）若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

【排序过程】
（1）在有向图中选一个无前驱（入度为0）的顶点且输出它。
（2）从图中删除该顶点和所有以它为尾的弧。
（3）重复（1）和（2），直至不存在无前驱的顶点。
（4）若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在环，否则输出的顶点序列即一个拓扑序列

【AOV网拓扑排序示例】
v₁ 和v₆ 没有前驱，则可任选一个。假设先输出 v₆，在删除 v₆ 及弧<v₆, v₄>、<v₆, v₅>之后，只有顶点 v₁ 没有前驱，则输出 v₁ 且删去 v₁ 及弧<v₁, v₂>、<v₁, v₃>和<v₁, v₄>，之后 v₃ 和 v₄ 都没有前驱。依次类推，可从中任选一个继续进行。

图4.3-AOV网及拓扑有序序列的过程

【Kahn算法实现拓扑排序步骤】
1.统计所有顶点的入度。
2.把所有入度为 0 的顶点压栈。
3.不断从栈里取顶点，输出到拓扑序列，并删除它的所有出边（相应邻接点入度 -1）。
4.如果有新的顶点入度变 0，就入栈。
5.循环直到栈空。
6.如果最后输出的顶点数 < 总顶点数，说明有环；否则拓扑排序成功。

Status TopologicalSort(ALGraph G, int topo[])
// 有向图 G用邻接表存储
// 若 G无回路，则生成一个拓扑序列 topo并返回 true；若 G有回路，则返回 false
{
    FindInDegree(G, indegree);  
    // 统计图中每个顶点的入度，存到 indegree[] 数组里

    InitStack(S);  
    // 初始化一个栈，用于存放“入度为 0 的顶点”

    for(i = 0; i < G.vexnum; ++i)　　　　
        if(!indegree[i]) 
            Push(S, i);
    // 将所有入度为 0 的顶点压入栈中（初始候选点）

    m = 0;　　
    // m 用来计数，记录输出到 topo 序列中的顶点个数

    while(!StackEmpty(S))  // 当栈非空时循环
    {　　　　　　　　 
        Pop(S, i);　
        // 弹出一个入度为 0 的顶点 i

        topo[m] = i;　
        ++m;　
        // 将顶点 i 放入拓扑序列，并增加计数

        p = G.vertices[i].firstarc;　
        // p 指向 i 的第一条出边

        while(p != NULL) 
        { 
            k = p->adjvex; 
            // k 是 i 指向的邻接点（即 i → k 这条边的终点）

            --indegree[k];
            // 删除边 i→k，相当于 k 的入度减 1

            if(indegree[k] == 0) 
                Push(S, k); 
            // 如果 k 的入度变为 0，说明它也可以进入拓扑序列，压入栈中

            p = p->nextarc;
            // 继续处理 i 的下一条出边
        } // while 
    } // while 

    if(m < G.vexnum) 
        return false; 
    // 如果输出的顶点数小于图的顶点数，说明图中存在环，无法拓扑排序

    else 
        return true;
    // 否则返回 true，topo[] 数组中就是一个拓扑序列
}

【算法分析】对有n个顶点和e条边的有向图而言，建立求各顶点入度的时间复杂度为O(e)；建立零入度顶点栈的时间复杂度为O(n)；有向图无环时每个顶点进一次栈，出一次栈，入度减1的操作在循环中总共执行 e 次，时间复杂度O(e)。整体语句频度约为 n+2e ，总的 时间复杂度为O(n + e)。

也可以理解为：拓扑排序不会“重复”扫描边。每个节点处理一次，每条边处理一次，因此是线性复杂度，和图的规模（点+边总数）成正比

关键路径

参考视频（❗强推）：一分钟求解关键路径、缩短工期问题 & 最大时间余量问题
代码实现非常长，大概率不会考关键路径的代码实现

1. 关键路径上的所有活动都是关键活动，它是决定整个工程的关键因素，因此 可通过加快关键活动来缩短整个工程的工期。但也不能任意缩短关键活动，因为一旦缩短到一定的程度，该关键活动就可能会变成非关键活动。
2. 网中的关键路径并不唯一且对于有几条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

【关键路径求解的过程】
（1）对图中顶点进行排序，在排序过程中按拓扑序列求出每个事件的最早发生时间ve(i)。
（2）按逆拓扑序列求出每个事件的最迟发生时间vl(i)。
（3）求出每个活动ai的最早开始时间e(i)。
（4）求出每个活动ai的最晚开始时间l(i)。
（5）找出e(i) = l(i)的活动ai，即关键活动。由关键活动形成的由源点到汇点的每一条路径就是关键路径，关键路径有可能不止一条。

（1）事件 v_i 的最早发生时间ve(i)：进入事件 v_i 的每一活动都结束，v_i 才可发生，所以ve(i)是从源点到 v_i 的最长路径长度。
（2）事件 v_i 的最迟发生时间vl(i)：事件 v_i 的发生不得延误 v_i 的每一后继事件的最迟发生时间。为了不拖延工期， v_i 的最迟发生时间不得迟于其后继事件 v_k 的最迟发生时间减去活动<v_i, v_k>的持续时间。
（3）活动a_i = <v_j, v_k>的最早开始时间e(i)：只有事件 v_j 发生了，活动 a_i 才能开始。所以，活动 a_i 的最早开始时间等于事件 v_j 的最早发生时间ve(j)。
（4）活动 a_i = <v_j, v_k>的最晚开始时间 l(i)：活动 a_i 的开始时间需保证不延误事件 v_k 的最迟发生时间。所以活动 a_i 的最晚开始时间 l(i) 等于事件 v_k 的最迟发生时间 vl(k) 减去活动 a_i 的持续时间 w_j,k
（5）活动 a_i 的时间余量：一个活动 a_i 的最迟开始时间 l(i) 和其最早开始时间 e(i) 的差值 l(i)−e(i) 。它是在不增加完成整个工程所需的总时间的情况下，活动 a_i 可以拖延的时间。

对于关键活动而言，e(i) = l(i) ；对于非关键活动，l(i)−e(i)的值是该工程的时间余量，在此范围内的适度延误不会影响整个工程的工期。

当一活动的时间余量为0时，说明该活动必须如期完成，否则就会拖延整个工期。所以称 l(i)−e(i) = 0，即 l(i) = e(i) 时的活动 a_i 是关键活动。