• “图”学习提纲

    文章目录

    前言

    “图”学习提纲。

    代码模板

    图的基本概念

    依据相关定义：

    • 图：点，边

    注意：图不可以为空图。即必须有点（有穷非空），不必须有边

    • 无向图，有向图：无向边，有向边/弧：弧尾，弧头
    • 简单图，多重图

    数据结构中一般讨论简单图：不存在顶点到自身的边，不存在重复的边

    • 完全图：无向完全图，有向完全图

    无向完全图：边数为n(n-1)/2。n为点数
    有向完全图：边数为n(n-1)。n为点数

    • 稀疏图，稠密图

    稀疏和稠密是相对而言的模糊概念

    • 带权图/网：权

    • 子图：生成子图

    依据点与边的关系：

    • 点的度，入度，出度

    对无向图：点的度的和=边数×2
    对有向图：点的入度的和=点的出度的和=边数；度=入度+出度

    • 有向树

    • 路径，路径长度，回路/环：简单路径，简单回路/环，最短路径/距离

    若图有n个点，大于n-1条边，则存在回路

    • 连通，连通图，非连通图，极大连通子图/连通分量

    若图有n个点，小于n-1条边，则为非连通图

    • 强连通，强连通图，强非连通图，极大强连通子图/强连通分量

    注意：对无向图，为连通性；对有向图，为强连通性

    • 极小连通子图/生成树，生成森林

    图的生成树有n-1条边，有n-1条边不一定是图的生成树。n为点数

    图的存储结构

    邻接矩阵

    类型：顺序存储结构

    组成：

    • 点数
    • 边数
    • 点一维数组：存储点数据
    • 边二维数组：存储数值，可存储权值

    创建的时间复杂度：

    • O(v²)。v为点数
    • O(v+v²+e) 。v为点数，e为边数。v为初始化点一维数组，v²为初始化边二维数组，e为给边赋值

    空间复杂度：

    • O(v²)。v为点数
    • O(v+v²)。v为点数。v为点一维数组，v²为边二维数组

    适用：稠密图

    相关性质：

    • 无向图：对称（可压缩存储上/下三角元素）；有效数值（如“1”表示点间存在边）数为边数的两倍；第i行或第i列的元素和为点i的度
    • 有向图：不对称；有效数值数为边数；第i行的元素和为点i的出度，第i列的元素和为点i的入度
    • 求点间是否有边：O(1)（依据点数据/下标取值）
    • 求点的邻边/邻接点：O(v)。v为点数（遍历点数据所在的一行）
    • 有权图：点到点有路径，数值为权值；点到当前点无路径，数值为0；点到其他点无路径，数值为无穷大
    • 存在邻接矩阵A，A的n次方的元素：A的n次方[i][j]=点i到点j中，长度为n的路径数
    • 邻接矩阵唯一

    邻接表

    类型：顺序和链式存储结构；关注点

    组成：

    • 点数
    • 边数
    • 点表：顺序存储结构；一维数组；单链表的头结点：存储点数据（当前点）和当前点指向第一个边结点的指针
    • （出）边表：链式存储结构；单链表；单链表的非头结点：存储点数据（其他邻接点）和当前点指向其他边结点的指针，可存储权值

    创建的时间复杂度：

    • O(v+e) 。v为点数，e为边数。v为初始化点表，e为初始化边表

    空间复杂度：

    • 无向图：O(v+2e)。v为点数，e为边数
    • 有向图：O(v+e)。v为点数，e为边数

    适用：稀疏图

    相关性质：

    • 求点的出度：遍历该点的链表
    • 求点的入度：遍历所有点的链表；使用逆邻接表
    • 求点间是否有边：O(v)。v为其他邻接点数。（遍历该点的链表）
    • 求点的邻边/邻接点：O(v)。v为其他邻接点数。（遍历该点的链表）
    • 邻接表不唯一

    邻接多重表

    类型：无向图的顺序和链式存储结构；关注边

    组成：

    • 点表：顺序存储结构；单链表的头结点；存储点数据（当前点）和当前点指向第一个边结点的指针
    • 边表：链式存储结构；单链表的非头结点；存储标志（可标记该边是否被搜索过），点i数据，点i（当前点）指向其他边结点的指针，点j数据（其他点），点j指向其他边结点的指针（“多重”的体现），可存储权值

    空间复杂度：

    • 无向图：O(v+2e)。v为点数，e为边数

    相关性质：

    • 易插入或删除边（相比于邻接表操作多个边结点，只需操作一个边结点）

    十字链表

    类型：有向图的顺序和链式存储结构

    组成：

    • 点表：顺序存储结构；单链表的头结点；存储点数据（当前点），以当前点为弧头的第一个边结点的指针，以当前点为弧尾的第一个边结点的指针
    • 边表：链式存储结构；单链表的非头结点；弧尾点（当前点）数据，弧头点（其他点）数据，弧尾点（当前点）指向弧头相同的边结点的指针，弧头点（其他点）指向弧尾相同的边结点的指针，可存储权值

    创建的时间复杂度：

    • O(v+e) 。v为点数，e为边数。v为初始化点表，e为初始化边表

    空间复杂度：

    • 有向图：O(v+e)。v为点数，e为边数

    相关性质：

    • 易求点的入度和出度
    • 图的十字链表不唯一，十字链表唯一确定图

    边集数组

    类型：顺序存储结构；关注边

    组成：

    • 点一维数组：存储点数据
    • 边一维数组：存储点（起点）数据，存储点（终点）数据，可存储权值

    相关性质：

    • 求点的度：遍历边一维数组
    • 适合依次操作边，不适合操作点

    图的遍历算法

    深度优先遍历（DFS）概述

    • 类似二叉树先序遍历
    • 是递归过程
    • 图的邻接矩阵唯一，广度优先遍历序列唯一；图的邻接表不唯一，广度优先遍历序列不唯
    • 保留遍历的边，删除未遍历的边，可形成深度优先遍历生成树（对连通图）或深度优先遍历生成森林（对非连通图）

    深度优先遍历（DFS）的过程

    1. 初始化标记数组（空间复杂度：O(v)。v为点数）
    2. 循环遍历点表，标记每点为未访问
    3. 循环遍历点表，若点的标记为未访问，则深度优先遍历图g，从点v开始（连通图执行一次，非连通图执行多次。非连通无向图执行连通分量数次，非强连通有向图的非强连通分量不一定能遍历所有点）
    4. 深度优先遍历g，从v开始
    5. 访问v（二叉树先序遍历的体现）
    6. 标记v已访问
    7. 循环获取v的邻接点w
    8. 循环中，若w的标记为未访问，则深度优先遍历g，从w开始（递归的体现）

    时间复杂度：依据存储结构

    • 对邻接矩阵：遍历点数×查找每点的邻接点的时间=O(v×v)=O(v²)。v为点数（理解：遍历每一行）
    • 对邻接表：遍历点数+查找每点的邻接点的时间=O(v+e)。v为点数，e为边数（理解：遍历点表和边表，因为是链式存储结构）

    空间复杂度：O(v)。v为点数/辅助空间规模/递归栈规模

    伪代码：

    bool visited[MAX_VERTEX_NUM];	//访问标记数组
void DFSTraverse(Graph G){		//对图G进行深度优先遍历
	for(int v=0;v<G.vexnum;++v)	
		visited[v] = FALSE;		//初始化已访问标记数据
	for(int v=0;v<G.vexnum;++v)	//本代码是从v=0开始遍历
		if(!visited[v])
			DFS(G,v);
}

void DFS(Graph G,int v){		//从顶点v出发，深度优先遍历图G
	visit(v);					//访问顶点v
	visited[v] = TRUE;			//设已访问标记
	for(w = FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
		if(!visited[w]){		//w为v的尚未访问的邻接顶点
			DFS(G,w);
		}	//if
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    广度优先遍历（BFS）概述

    • 类似二叉树层序遍历
    • 是迭代过程
    • 图的邻接矩阵唯一，广度优先遍历序列唯一；图的邻接表不唯一，广度优先遍历序列不唯一
    • 保留遍历的边，删除未遍历的边，可形成广度优先遍历生成树（对连通图）或广度优先遍历生成森林（对非连通图）
    • 类似迪杰斯特拉（Dijkstra）单源最短路径算法
    • 类似普里姆（Prim）最小生成树算法

    广度优先遍历（BFS）的过程

    1. 初始化标记数组（空间复杂度：O(v)。v为点数）
    2. 循环遍历点表，标记每点为未访问
    3. 初始化队列（空间复杂度：O(v)。v为点数）
    4. 循环遍历点表，若点的标记为未访问，则广度优先遍历图g，从点v开始（连通图执行一次，非连通图执行多次。非连通无向图执行连通分量数次，非强连通有向图的非强连通分量不一定能遍历所有点）
    5. 广度优先遍历g，从v开始
    6. 访问v
    7. 标记v已访问
    8. v入队
    9. 当队列不为空时，循环
    10. 循环中，获取v的所有邻接点w（迭代的体现）
    11. 循环中，若w的标记为未访问，则访问w，标记w已访问，w入队（二叉树层序遍历的体现）

    时间复杂度：依据存储结构

    • 对邻接矩阵：遍历点数×查找每点的邻接点的时间=O(v×v)=O(v²)。v为点数（理解：遍历每一行）
    • 对邻接表：遍历点数+查找每点的邻接点的时间=O(v+e)。v为点数，e为边数（理解：遍历点表和边表，因为是链式存储结构）

    空间复杂度：O(v)。v为点数/辅助空间规模

    伪代码：

    bool visited[MAX_VERTEX_NUM];		//访问标记数组
bool BFSTraverse(Graph G){			//对图G进行广度优先遍历
	for(int i=0;i<G.vexnum;++i)
		visited[i] = FALSE;			//访问标记数组初始化
	InitQueue(Q);					//初始化辅助队列Q
	for(int i=0;i<G.vexnum;++i){	//从0号顶点开始遍历
		if(!visited[i])				//对每个连通分量调用一次BFS
			BFS(G,i);				//vi未访问过，从vi开始BFS
	}
}
 
void BFS(Graph G,int v){			//从顶点v出发，广度优先遍历图G
	visit(v);						//访问初始顶点v
	visited[v] = TRUE;				//对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))	
									//检测v所有邻接点
			if(!visited[w]){		//w为v的尚未访问的邻接顶点 
				visit[w];			//访问顶点w 
				visited[w] = TRUE;	//对w做已访问标记
				EnQueue(Q,w);		//顶点w入队列 
			}//if
	}//while
}

    • 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

    图的应用

    最小（代价）生成树概述

    概念：

    • 对连通图
    • 是极小连通子图
    • 有图的所有点，尽量少的边
    • 若少一条边，则成非连通图；若多一条边，则存在回路

    性质：

    • 边数=点数-1
    • 树形不唯一。若图中各边权值不相等，则唯一；若图中存在相等权值的边，构造时都被加入树中，则唯一
    • 边权值的和唯一且最小

    构造算法：基于贪心思想；对无向图

    • 普里姆（Prim）算法
    • 克鲁斯卡尔（Kruskal）算法

    构造算法的伪代码：

    GENERIC MST(G){
	T=NULL;
	while T未形成一棵生成树；
		do 找到一条最小代价边(u,v)并且加入T后不会产生回路；
			T=T∪(u,v);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    最小（代价）生成树的普里姆（Prim）算法

    概述：

    • 类似图的最短路径的迪杰斯特拉（Dijkstra）算法
    • 对点

    过程：选边加点加边

    1. 加点
    2. 加候选边
    3. 依据代价，从候选边中选边（每次构造一定为连通图）
    4. 依据所选边，加点
    5. 依据所加点，加候选边
    6. 重复345步，直到加入所有点（执行n-1次，n为点数）

    伪代码：

    void Prim(G,T){
	T=空集;						//初始化空树
	U={w};						//添加任一顶点w 
	while((V-U)!=空集){			//若树中不含全部顶点
		设(u,v)是使u属于U与v属于(V-U),且权值最小的边；
		T=T∪{(u,v)}				//边归入树
		U=U∪{v};				//顶点归入树
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    时间复杂度：O(n²)。n为点数

    空间复杂度：O(n)。n为点数。辅助空间记录标记已访问点和候选边

    适用：边稠密图

    最小（代价）生成树的克鲁斯卡尔（Kruskal）算法

    概述：

    • 对边

    过程：加边加点；合并点/连通分量/树

    1. 依据代价，排序边
    2. 依据代价，从小到大遍历边
    3. 若边为候选边，则加边（每次构造不一定为连通图）
    4. 依据所加边，若点为候选点，则加点，否则不加边不加点并转2
    5. 重复234步，直到直到加入n-1条边。n为点数/所有点在一个连通分量

    若边为候选边和若点为候选点的另一种描述：若加边不构成回路，则加边加点，否则不加边不加点并转2

    伪代码：

    void Kruskal(V,T){
	T=V;					//初始化树T，仅含顶点
	numS=n;					//连通分量数
	while(numS>1){			//若连通分量数大于1 
		从E中取出权值最小的边(v,u);
		if(v和u属于T中不同的连通分量){
			T=T∪{(v,u)};	//将此边加入生成树中
			numS--;			//连通分量数减1 
		}
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    时间复杂度：排序算法中常用堆排序，堆存储边：O(eloge)。e为边数

    空间复杂度：O(n)。n为点数。辅助空间并查集记录点的树型结构

    适用：边稀疏点稠密图/稀疏图

    最短路径概述

    概念：

    • 对带权图
    • 带权路径长度最短的路径

    算法：

    • 迪杰斯特拉（Dijkstra）算法
    • 弗洛伊德（Floyd）算法

    最短路径的迪杰斯特拉（Dijkstra）算法

    概述：

    • 类似图的最小（代价）生成树的普里姆（Prim）算法
    • 对点
    • 基于贪心策略

    思想：求单源最短路径：图中某点到其他点的最短路径

    求多源最短路径：图中多点到其他点的最短路径。时间复杂度：O(n×n²)=O(n的3次方)。n为点数

    过程：选边加点加边

    1. 加点
    2. 加候选边
    3. 依据代价，从候选边中选边（每次构造一定为连通图）
    4. 依据所选边，加点
    5. 依据所加点，加候选边，更新代价
    6. 重复345步，直到加入所有点（执行n-1次，n为点数）

    伪代码：

    void Dijkstra(MGraph g,int v,int dist[],int path[])
{
    int set[maxSize];
    int min, i, j, u;
    /*从这句开始对各数组进行初始化*/
    for(i=0;i<g.n;++i)
    {
        dist[i]=g.edges[v][i];
        set[i]=0;
        if(g.edges[v][i]<INF)
            path[i]=v;
        else
            path[i]=-1;
    }
    set[v]=1;path[v]=-1;   
    /*初始化结束*/
    /*关键操作开始*/
    for(i=0;i<g.n-1;++i)
    {
        min=INF;
        /*这个循环每次从剩余顶点中选出一个顶点，通往这个顶点的路径在通往所有剩余顶点的路径中是长度最短的*/
        for(j=0;j<g.n;++j)
        {
            if(set[j]==0&&dist[j]<min)
            {
                u=j;
                min=dist[j];
            }
        }
        set[u]=1;	//将选出的顶点并入最短路径中
        /*这个循环以刚并入的顶点作为中间点，对所有通往剩余顶点的路径进行检测*/
        for(j=0;j<g.n;++j)
        {
            /*这个if语句判断顶点u的加入是否会出现通往顶点j的更短的路径，如果出现，则改变原来的路径及其长度，否则什么都不做*/
            if(set[j]==0&&dist[u]+g.edges[u][j]<dist[j])
            {
                dist[j]=dist[u]+g.edges[u][j];
                path[j]=u;
            }
        }
    }    
    /*关键操作结束*/
}
/*函数结束时，dist[]数组中存放了v点到其余顶点的最短路径长度，path[]中存放v点到其余各顶点的最短路径*/

    • 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
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44

    时间复杂度：O(n²)。n为点数

    空间复杂度：O(n)。n为点数。辅助空间记录点间代价，路径中点的前一点和标记已访问点

    适用：非带权图；不存在负权值的带权图

    最短路径的弗洛伊德（Floyd）算法

    思想：求点间的最短路径

    过程：迭代

    1. 初始化代价矩阵为邻接矩阵，路径矩阵
    2. 遍历点
    3. 对所遍历点，遍历点对
    4. 对遍历点对，所遍历点作为中间点，依据代价，更新代价矩阵和路径矩阵
    5. 重复234步，直到遍历所有点（执行n-1次，n为点数）

    伪代码：

    void Floyd(MGraph *g,int Path[][maxSize],int A[][maxSize])
{	//图g的边矩阵中，用INF来表示两点之间不存在边
    int i,j,k;    
    /*这个双循环对数组A[][]和Path[][]进行了初始化*/
    int A[MAXSIZE][MAXSIZE] = { 0 };
    for(i=0;i<g->n;++i)
    {
        for(j=0;j<g->n;++j)
        {
            A[i][j]=g->edges[i][j];
            Path[i][j]=-1;
        }
    }
    /*下面这个三层循环是本算法的主要操作，完成了以k为中间点对所有的顶点对(i,j)进行检测和修改*/
    for(k=0;k<g->n;++k)
    	for(i=0;i<g->n;++i)
        	for(j=0;j<g->n;++j)
            {
                if(A[i][j]>A[i][k]+A[k][j])
                	Path[i][j] = k;
            }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    时间复杂度：O(n的3次方)。n为点数

    空间复杂度：O(n²)。辅助空间记录代价和路径

    适用：非带权图；可存在负权值，负权值边不成回路的带权图

    拓扑排序概述

    顶点表示活动的网/活动在顶点上的网（AOV网）：

    • 工程中，各活动间先后关系的有向无环图
    • 无回路的有向图/有向无环图/DAG图表示工程，点表示活动，边表示活动的先后关系

    有向无环图可类比树，使用表达式描述

    算法：拓扑排序

    拓扑排序算法

    概念：

    • 对有向无环图，构造拓扑排序序列的过程
    • 每点访问且仅访问一次
    • 若图中存在点A到点B的路径，则拓扑排序序列中点A在点B的前面

    过程：

    1. 选择一个没有前驱/入度为0的点，输出
    2. 删除该点和以该点为起点的有向边
    3. 重复12步，直到AOV网为空（排序成功）或AOV网不为空且不存在没有前驱/入度为0的点（存在回路，排序失败）

    伪代码：

    int TopSort(AGraph *G)
{
    int i,j,n=0;
    int stack[maxSize],top=-1;	//定义并初始化栈
    ArcNode *p;
    /*这个循环将图中入度为0的顶点入栈*/
    for(i=0;i<G->n;++i)			//图中顶点从0开始编号
        if(G->adjlist[i].count==0)
        	stack[++top]=i;
    /*关键操作开始*/
    while(top!=-1)
    {
        i=stack[top--];			//顶点出栈
        ++n;    				//计数器加一，统计当前顶点
        cout<<i<<" ";			//输出当前顶点
        p=G->adjlist[i].firstarc;
        /*这个循环实现了将所有由此顶点引出的边所指向的顶点的入度都减少1，并将这个过程中入度变为0的顶点入栈*/
        while(p!=NULL)
        {
            j=p->adjvex;
            --(G->adjlist[j].count);
            if(G->adjlist[i].count==0)
            {
                stack[++top]=j;
            }
            p=p->nextarc;
        }
    }
    /*关键操作结束*/
    if(n==G->n)
        return 1;
    else 
    	return 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
    • 31
    • 32
    • 33
    • 34

    时间复杂度：依据存储结构

    • 对邻接矩阵：O(n²)。n为点数（理解：遍历每一行）
    • 对邻接表：O(n+e)。n为点数，e为边数（理解：遍历点表和边表，因为是链式存储结构）

    空间复杂度：O(n)。n为点数。辅助空间栈记录前驱/入度为0点

    其他：

    • 拓扑排序序列不唯一。因为可能同时存在多个入度为0的点，选择不同，序列不同
    • 因为点地位平等，由人工编号，所以可依据拓扑排序序列对点重新编号，生成新邻接矩阵，该邻接矩阵可为三角矩阵
    • 对一般图，若邻接矩阵是三角矩阵，则存在拓扑排序序列，反之不一定
    • 拓扑排序：对入度
    • 逆拓扑排序：对出度
    • 若有向图无回路，则可用深度优先遍历进行拓扑排序，深度优先遍历序列为拓扑排序序列
    • 判断有向图有回路的方法：深度优先遍历；拓扑排序

    关键路径概述

    边表示活动的网/活动在边上的网（AOE网）：

    • 工程中，各活动持续时间的有向无环图
    • 无回路的有向图/有向无环图/DAG图表示工程，边表示活动，边的权值表示活动的持续时间；点表示事件（新活动开始或旧活动结束的标志）

    注意：AOV网的边无权值

    AOE网的性质：

    • 只有点表示的事件发生后，以该点为起点的边表示的活动才能开始
    • 只有所有以该点为终点的边表示的活动结束后，该点表示的事件才能发生

    相关概念：

    • 源点：入度为0的点，只有一个
    • 汇点，出度为0的点，只有一个
    • 关键路径：从源点到汇点的所有路径中，有最长/大路径长度的，最短完成工程时间的路径（重点理解）
    • 最长/大路径长度理解：只有所有最久持续时间的活动结束，工程才结束
    • 最短完成工程时间理解：要想工程结束，最少/必须经过的时间
    • 关键活动：关键路径上的活动

    注意：

    • 关键活动决定工程。可缩短关键活动的持续时间，以缩短工程的工期；可延长关键活动的持续时间，以延长工程的工期
    • 不能任意缩短关键活动的持续时间。若缩短到一定程度，则关键活动可能成为非关键活动
    • 关键路径可能不唯一
    • 若AOE网存在多条关键路径，缩短一条关键路径上关键活动的持续时间不一定能缩短工程的工期（因为关键活动可能成为非关键活动，关键路径可能成为非关键路径）；缩短所有关键路径上共有的关键活动能缩短工程的工期
    • 无论AOE网存在一条或多条关键路径，延长任一条关键路径上任一个关键活动的持续时间能延长工程的工期

    算法：求关键路径

    关键路径算法

    算法的参量（重点理解）：

    • 事件的最早发生时间：源点到点的最长路径长度（理解：只有最久的准备事件结束，才能开始当前事件）
    • 事件的最晚发生时间：汇点到点的最短路径长度（理解：要想准时开始当前事件，只有最早开始准备事件）
    • 活动的最早发生时间：边起点表示事件的最早发生时间（理解：只要事件开始，活动就开始）
    • 活动的最晚发生时间：边终点表示事件的最晚发生时间-该边表示活动的持续时间（理解：事件最晚开始时间，减活动持续时间，得活动最晚开始时间）
    • 活动的剩余时间：活动的最晚发生时间-活动的最早发生时间（反映活动完成的松紧度）
    • 关键活动：活动的剩余时间=0
    • 关键路径：关键活动构成的路径

    过程：

    1. 拓扑排序
    2. 依据拓扑排序序列，顺序求各点表示事件的最早发生时间（从前往后；源点表示事件的最早发生时间等于0）
    3. 逆拓扑排序
    4. 依据逆拓扑排序序列，顺序求各点表示事件的最晚发生时间（从后往前；汇点表示事件的最晚发生时间等于事件的最早发生时间）
    5. 求各点/边表示活动的最早发生时间
    6. 求各点/边表示活动的最晚发生时间
    7. 求活动的剩余时间/关键活动
    8. 求关键路径

    总结

    “图”学习提纲。

    参考资料

    • 《2023版数据结构高分笔记》主编：率辉
    • 《2023年计算机组成原理考研复习指导》组编：王道论坛
    • 《大话数据结构》作者：程杰

    作者的话

    • 感谢参考资料的作者/博主
    • 作者：夜悊
    • 版权所有，转载请注明出处，谢谢~
    • 如果文章对你有帮助，请点个赞或加个粉丝吧，你的支持就是作者的动力~
    • 文章在描述时有疑惑的地方，请留言，定会一一耐心讨论、解答
    • 文章在认识上有错误的地方, 敬请批评指正
    • 望读者们都能有所收获
  • 相关阅读:
    Java基础常见面试题总结
    Explore EP9162S HDMI 分配器
    在linux上做移动开发必须知道这五个
    ESP8266-Arduino编程实例-TSL2561亮度传感器驱动
    双亲委派机制的理解学习
    Django--Learning and understanding
    CSS（上）
    ZYNQ之FPGA学习----UART串口实验
    R | R包默认安装路径的查看及修改
    Spring AOP以及统一处理
  • 原文地址：https://blog.csdn.net/m0_62083249/article/details/127154405