-
数据结构第六章图部分知识点
图的存储结构
后面测试用例示例
邻接矩阵法——空间复杂度很高，顺式存储
// 邻接矩阵法 #define MaxVertexNum 100 typedef struct{ char vex[MaxVertexNum];//顶点表 int edge[MaxVertexNum][MaxVertexNum];//邻接矩阵，边数 int vexnum,arcnum;//图的当前顶点数和边数/弧数 }MGraph;- 1
- 2
- 3
- 4
- 5
- 6
- 7
-
无权图
有对应的边则数组的值为1，没有对应的边数组值为0。
对于无向图，二维数组一定是一对称矩阵，因为两点顶点相邻，无方向，当求其结点的度的时候只需要遍历数组的一行或者一列看有多少个1便可以了，时间复杂度为O(n)。
对于有向图，二维数组不一定是对称矩阵，因为边是有方向的。如果要求有向图结点的入度，需要遍历结点对应的列，如果要求结点的出度，需要遍历结点对应的行，结点的度=入度+出度，时间复杂度为O(n)。 -
带权图
对应边的数组值为权值，没有对应边的数组值为0或者∞ -
性能分析
空间复杂度：存储n个顶点：O(n)；存储其对应的边：O(n^2)
适合存储稠密图，有向图可以采用对称矩阵压缩存储的方法进一步压缩矩阵 -
邻接矩阵法的性质——离散数学内容
得到的结果表示各个结点长度为n的路径信息
邻接矩阵的创建
- 直接按照前面给出的实例写死的一个矩阵，无实际意义，仅仅是为了后面写代码测试方便
// 初始化邻接矩阵 void initMGraph(MGraph *mGraph){ (*mGraph).vexnum=0; (*mGraph).arcnum=0; } // 不严谨的邻接矩阵法定义一个无向图 void createMGraph1(MGraph *mGraph){ (*mGraph).vexnum=5; (*mGraph).arcnum=6; for(int i=0;i<(*mGraph).vexnum;i++){ (*mGraph).vex[i]=65+i;//输入的是字母的ASCII码，会转化的 } //对称矩阵 // 结构体定义之后再对数组进行初始化，是不能用{}进行赋值的。下面注释是会报错的代码 // (*mGraph).edge[vexnum][vexnum]={{0,1,1,1,1},{1,0,1,0,0},{1,1,0,1,0},{1,0,1,0,0},{1,0,0,0,0}}; int temp[5][5]={{0,1,1,1,1},{1,0,1,0,0},{1,1,0,1,0},{1,0,1,0,0},{1,0,0,0,0}}; for(int i=0;i<(*mGraph).vexnum;i++){ for(int j=0;j<(*mGraph).vexnum;j++){ (*mGraph).edge[i][j]=temp[i][j]; } } } // 创建一个有向图的邻接矩阵 void createMGraph2(MGraph *mGraph){ (*mGraph).vexnum=5; (*mGraph).arcnum=6; for(int i=0;i<(*mGraph).vexnum;i++){ (*mGraph).vex[i]=65+i;//输入的是字母的ASCII码，会转化的 } int temp[5][5]={{0,1,1,1,1},{0,0,1,0,0},{0,0,0,1,0}}; for(int i=0;i<(*mGraph).vexnum;i++){ for(int j=0;j<(*mGraph).vexnum;j++){ (*mGraph).edge[i][j]=temp[i][j]; } } } // 打印邻接矩阵定义的图 void printfMGraph(MGraph mGraph){ printf("邻接矩阵的顶点集……\n"); for(int i=0;i<mGraph.vexnum;i++){ printf("[%d]-[%c]\n",i,mGraph.vex[i]); } printf("邻接矩阵的边集……\n"); for(int i=0;i<mGraph.vexnum;i++){ for(int j=0;j<mGraph.vexnum;j++){ printf("%d ",mGraph.edge[i][j]); } printf("\n"); } // printf("\n"); }- 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
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
按照无向图到有向图顺序打印结果
邻接表——顺序+链式存储
// 领接表法——和树的孩子表示法类似 // ‘边、弧’ typedef struct arcNode{ int adjvex;//指向哪一个结点 struct arcNode *next;//指向下一条弧的指针 }arcNode; // ‘顶点’ typedef struct vNode{ vertexType data;//顶点信息 arcNode *first;//第一条弧 }vNode,adjList[MaxVertexNum]; // 用邻接表存储的图 typedef struct{ adjList vertices;//表征的是顶点的集合 int vexnum,arcnum; }ALGraph;- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
实现从邻接矩阵存储图转化为邻接表存储图
// 初始化邻接表 void initALGraph(ALGraph *alGraph){ (*alGraph).vexnum=0; (*alGraph).arcnum=0; } // 给出顶点的值，寻找邻接矩阵中顶点值的对应下标并返回 int indexof(MGraph mGraph,vertexType vex){ for(int i=0;i<mGraph.vexnum;i++){ if(mGraph.vex[i]==vex) return i; } return -1;//表示下标不存在 } // 根据邻接矩阵图创建图的邻接表法表示 void creatALGraph(MGraph mGraph,ALGraph *alGraph){ (*alGraph).vexnum=mGraph.vexnum;//修改顶点数量和边的数量 (*alGraph).arcnum=mGraph.arcnum; for(int i=0;i<mGraph.vexnum;i++){ // 处理顶点 vNode *vex=(vNode *)malloc(sizeof(vNode));//申请一个顶点空间 vex->data=mGraph.vex[i]; vex->first=NULL; //处理边 int index=indexof(mGraph,vex->data);//寻找对应的顶点的对应行坐标 arcNode *p=vex->first;//指针指向 for(int j=0;j<mGraph.vexnum;j++){ if(mGraph.edge[index][j]==1){//表示有数据 // 申请一个边结点 arcNode* arc=(arcNode*)malloc(sizeof(arcNode)); arc->adjvex=j; arc->next=NULL; if(p==NULL){//说明是第一个节点边 vex->first=arc; p=arc; }else{ p->next=arc; p=p->next; } } } (*alGraph).vertices[i]=*vex; } printfALGraph(*alGraph); } // 打印邻接表边 void printfArc(arcNode *arc){ arcNode *p=arc; while(p!=NULL){ printf("%d->",p->adjvex); p=p->next; } printf("\n"); } // 打印邻接表定义的图 void printfALGraph(ALGraph alGraph){ printf("邻接表打印,数字表示的是结点对应下标……\n"); for(int i=0;i<alGraph.vexnum;i++){ printf("|%c|->",alGraph.vertices[i].data); printfArc(alGraph.vertices[i].first); } }- 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
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
图的基本操作
Adjacent(G, x, y)：判断图 G 是否存在边
Neighbors(G, x)：列出图 G 中与结点 x 邻接的边
InsertVertex(G, x)：在图 G 中插入顶点 x
DeleteVertex(G, x)：从图 G 中删除顶点 x
AddEdge(G, x, y)：若无相边 (x, y) 或有向边
RemoveEdge(G, x, y)：若无相边 (x, y) 或有向边
FirstNeighbor(G, x)：求图 G 中顶点 x 的第一个邻接点，若有则返回顶点号。若 x 没有邻接点或图中不存在 x，则返回 -1NextNeighbor(G, x, y)：假设图 G 中顶点 y 是顶点 x 的一个邻接点，返回除 y 之外顶点 x 的下一个临界点的顶点号，若 y 是 x 的最后一个邻接点，则返回 -1
Get_edge_value(G, x, y)：获取图 G 中边 (x, y) 或
Set_edge_value(G, x, y, v)：设置图 G 中边 (x, y) 或#include "graph.h" // 求图中顶点x的第一个邻接点，有就返回顶点号——邻接矩阵示例 int firstNeighbor1(MGraph mGraph,vertexType x){ int index=indexof1(mGraph,x); for(int i=0;i<mGraph.vexnum;i++){ if(mGraph.edge[index][i]==1) return i; } return -1;//表示没有第一个邻接点 } // 给出邻接表的一个顶点，返回其下标表示 int indexof2(ALGraph alGraph,vertexType vex){ for(int i=0;i<alGraph.vexnum;i++){ if(alGraph.vertices[i].data==vex) return i; } return -1; } // 邻接矩阵示例 int firstNeighbor2(ALGraph alGraph,vertexType x){ int index=indexof2(alGraph,x); if(alGraph.vertices[index].first!=NULL) return (alGraph.vertices[index].first)->adjvex; else return -1; } // 返回图顶点x的除了y之外的下一个邻接点的顶点号，如果y是最后一个就返回-1——邻接矩阵示例 int nextNeighbor1(MGraph mGraph,vertexType x,vertexType y){ int index=indexof1(mGraph,x); int j=indexof1(mGraph,y);//y对应的下标值 int i=j+1; for(;i<mGraph.vexnum;i++){ if(mGraph.edge[index][i]==1){ // printf("%d",i); break;//找到对应的内容，就结束循环 } } if(i==mGraph.vexnum)//刚好是最后一个邻接点 return -1; return i;//不是最后一个邻接点,直接返回其下标，在本测试用例中所有结点按照字母顺序排序，对于不按照字母排序的图，只要其顶点表和边表的结点下标是对应的（应该没有不对应的），就可以用直接返回下标实现返回结点下标 } // 返回图顶点x的除了y之外的下一个邻接点的顶点号，如果y是最后一个就返回-1——邻接表示例 int nextNeighbor2(ALGraph alGraph,vertexType x,vertexType y){ int index=indexof2(alGraph,x); int j=indexof2(alGraph,y); arcNode *p=alGraph.vertices[index].first; while(p!=NULL){ if(p->adjvex==j){ if(p->next==NULL)//表示没有下一个邻接点 return -1; else return p->next->adjvex; } p=p->next; } }- 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
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
图的遍历
下面遍历的伪代码中 FirstNeighbor(G,v);w>=0和 NextNeighbor(G,v,w)实现有点不同，但是实际上，图的存储结点不一定就是int类型数据或者char类型数据，所以还是要根据具体要求来实现
BFS
bool visited[MAX_VERTEX_NUM];//访问标记数组 //对于非连通图，也可以实现BFS void BFSTraverse(Graph G){ for(int i=0;i<G.vexnum;i++){//初始化标记数组 visited[i]=false; } InitQueue(Q);//初始化辅助队列 for(int i=0;i<G.vexnum;i++){ if(!visited[i]) BFS(G,i);//从顶点i开始进行BFS } } //从顶点v出发，广度优先遍历图G void BFS(Graph G,int v){ visit(v);//访问初始顶点v visited[v]=true; EnQueue(Q,v); while(!isEmpty(Q)){ DeQueue(Q,v); for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){ if(!visited[w]){ visit(w); visited[w]=true; EnQueue(Q,w); } } } }- 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
DFS
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);//从顶点i开始进行BFS } } void DFS(Graph G,int v){ visit(v); visited[v]=true; for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){ if(!visited[w]){ DFS(G,w); } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
复杂度分析
广度优先搜索需要借助辅助队列，而深度优先遍历需要借助递归栈，所以无论是邻接矩阵还是邻接表，都需要O(|V|)的空间复杂度
采用邻接表法存储图进行搜索时，每个顶点需要搜索一遍，时间复杂度是O(|V|)，遍历时每条边也需要遍历一遍，时间复杂度为O(|E|)，所以总的时间复杂度为O(|V|+|E|)
采用邻接矩阵法存储图进行搜索时，需要遍历全部的顶点，在遍历每个顶点时，查找每个顶点的邻接点需要再遍历一遍结点，所以时间复杂度为O(|V|^2)
实际上时间复杂度的要求，取决于其使用的存储结构
最小生成树MST
生成树：包含图的全部顶点的一个极小连通子图
包括广度优先生成树和深度优先生成树以及最小生成树，最小生成树可能有多个- 无权图或者权值相同的图
对于无权图或者权值相同的图，无论怎么选边，最小生成树权值之和都是边的权值*(边数-1)
prim算法(普里姆)
从某一个顶点开始构建生成树，每次都将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止——先选点，适合点少边多的边稠密图，时间复杂度为O(|V|^2)
同一个图可能有多个最小生成树算法实例
Kruskal算法(克鲁斯卡尔)
每次选择一条权值最小的边，使得边的两头连通，原本就连通的就不选，直到左右的点都连通——先选边，适合边少点多的边稀疏图，时间复杂度为O(|E|log2|E|)(一共有e的边，每次都需要用并查集判断两个顶点是否属于同一个集合，需要long2E的时间复杂度)
算法示例
在检查是否连通的这点上，使用到了并查集，并查集采用的是树的双亲表示法。
最短路径问题
单源最短路径问题
- 无权图——使用广度优先算法求无权图单源最短路径问题
void BFS_MIN_Distance(Graph G,int u){ //新增一个数组，包含两个部分d[i]表示从u到i的最短路径，path[i]表示最短路径是从哪个顶点过来的 for(i=0;i<G.vexnum;i++){ //初始化数组 d[i]=无穷大; path[i]=-1; } d[u]=0;//把u顶点放到队列中，因为是第一个顶点所以路径是0 visited[u]=true; EnQueue(Q,u); while(!isEmpty(Q)){ 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;//最短路径从u到w visited[w]=true;//标记已访问 EnQueue(Q,w);//顶点w入队 } } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
通过新添加的数组中d[w]可以快速查找u到w的最短路径长度，通过path[w]字段可以快速查找所需路径的前一个结点，通过查找前一个结点的方式循环查找前一个结点直到找到根节点，由此可以找到其最短路径。
通过广度优先遍历得到的广度优先树的高度一定是最小的。
- 有权图——Dijkstra算法(迪杰斯特拉)
每次选择的都是权值最小的那个对应顶点开始计算
并且每次被选中的结点在后面的循环中其最小距离不会发生改变，根据这个特性可以求迪杰斯特拉算法求的最小路径的的结点的顺序
带权路径长度：当图带全图时，一条路径上所有边的权值之和，称为该路径的带权路径长度
Dijkstra算法(迪杰斯特拉)：也适用于无权图或者权值相同的图
算法实例
初始化信息的备注：v0到v0肯定是可达的，且距离就是0。
因为v0到v1和v4都是可达的，所以路径信息可以直接初始化
时间复杂度
遍历每一个顶点的时候还要遍历其他的顶点，所以时间复杂度为O(|v|^2)
- 带负权值的带权图
如果权值带负数，迪杰斯特拉算法可能会失效，找不到最优路径
顶点间求最短路径——Floyd算法
Floyd算法：适合于带权图或者无权图——动态规划
动态规划：将问题求解分为多个阶段，每个阶段都有一定的递进关系
算法示例：
算法初始化的时候，各个顶点的最短路径长度为邻接矩阵的形式，因为不允许中转
使用V0作为中转，V2存在经过V0到达V1的路径，长度为11，前一个结点为V0，因此需要修改对应的两个值
对于允许以V0和V1作为中转点的实现，对于V0到V2的路径中可以有V0-V1-V2的路径，长度为10，因此需要修改两个值。
允许所有结点中转，从V1到V0可以中转V2，有对应路径长度为9
经过|V|论递推实现，最终得到的两个二维数组就是动态规划得到的最终结果
//核心代码 for(int k=0;k<n;k++){//考虑以Vk作为中转 for(int i=0;i<n;i++){//遍历整个矩阵 for(int j=0;j<n;j++){ if(A[i][j]>A[i][k]+A[k][j]){//表示路径更短 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
算法时间复杂度为O(|V|3)，
空间复杂度为O(|V|2)
这个算法整合中转的时候，只需要整合在邻接矩阵(修改前后都可以)中对应顶点的行在中转顶点所在的列中是否有非0或者非∞的数据即可
可以解决带负权值的图，不能解决带有负权回路的图
有向无环图
若一个有向图中不存在环，称为有向无环图，简称DAG
正确答案是A
对于有向无环图的做题：
顶点中不可能出现重复的操作数
拓扑排序-顶点表示活动
AOV网：用DAG（有向无环图）表示一个工程，顶点表示活动
拓扑排序：找到做事的先后顺序，可能有多个拓扑排序
拓扑排序的实现:
①从AOV网中选择一个没有前驱(入度为0)的顶点并输出。
②从网中删除该顶点和所有以它为起点的有向边。
③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。后者说明图中有回路，不是DAG
- 使用邻接表存储实现拓扑排序
indegree[i]：表示i结点的入度是多少
print[i]：用来记录拓扑排序序列，当有结点出栈的时候，printf数组就会记录一次，初始化时都是-1
bool TopologicalSort(Graph G){ InitStack(S);//初始化栈，存储入度为0的顶点 for(int i=0;i<G.vexnum;i++){ if(indegree[i]==0) Push(S,i);//将所有入度为0的顶点入栈 } int count=0;//计数，记录当前已经输出的顶点数 while(!isEmpty(S)){//存在入度为0的顶点 Pop(S,i);//栈顶元素出栈 print[count++]=i;//输出顶点元素i //for：将所有i指向的顶点的入度减1(主要是修改indegree数组，图邻接表本身没变)，并且将入度为0的顶点入栈 for(p=G.vertices[i].firstarc;p;p=p->nextarc){ v=p->adjvex; if(!(--indegree[v])) Push(S,v);//入度为0，出栈 } } if(count<G.vexnum) return false;//拓扑失败，说明有向图中存在回路 else return true;//拓扑成功 }- 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
时间复杂度：O(|V|+|E|)
如果用邻接矩阵实现，时间复杂度为O(|V|2)
逆拓扑排序
对一个AOV网，如果采用下列步骤进行排序，则称之为逆拓扑排序:
①从AOV网中选择一个没有后继(出度为O)的顶点并输出。
②从网中删除该顶点和所有以它为终点的有向边。
③重复①和②直到当前的AOV网为空。
用邻接矩阵实现比用邻接表实现具有更少的时间复杂度，或者可以采用逆邻接表法，也就是邻接表记录的是每个顶点的入度边
用DFS实现拓扑排序
bool visited[MAX_SIZE]; int finishTime[MAX_SIZE]; void DFSTraverse(Graph G){ for(v=0;v<G.vexNum;v++){ visited[v]=false; } int time=0; for(v=0;v<G.vexNum;v++){ if(!visited[v]){ DFS(G,v); } void DFS(Graph G,int v){ visited[v]=true; visit(v); for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){ if(!visited[w]){ DFS(G,w); } } time=time+1; finishTime[v]=time; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
用DFS实现逆拓扑排序
只是多一个输出代码而已
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);//从顶点i开始进行BFS } } void DFS(Graph G,int v){ visit(v); visited[v]=true; for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){ if(!visited[w]){ DFS(G,w); } } printf(v);//输出顶点***在DFS基础上新增的 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
现在在这个基础上，需要判断图中是都有回路问题，方法是：邻接点如果已经被访问了且存在于栈中，说明存在环路，可采用一个数组来表示当前一次循环中入栈的元素，这样就可以实现快速查找是否当前下一个结点是被访问且已经存在于栈中的。
bool visited[MAX_VERTEX_NUM];//访问标记数组 bool isStack[MAX_VERTEX_NUM];//当前结点是否在栈中 bool balance=true;//判断是否拓扑成功，初始化认为是拓扑成功的 void DFSTraverse(Graph G){ for(int i=0;i<G.vexnum;i++){//初始化标记数组和isStack数组 visited[i]=false; isStack[i]=false; } for(int i=0;i<G.vexnum;i++){ if(balance==false) break;//拓扑失败，可以直接结束 if(!visited[i]) DFS(G,i);//从顶点i开始进行BFS } } void DFS(Graph G,int v){ visit(v); visited[v]=true; isStack[v]=true; for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){ if(visited[w]&&isStack[w]){//被访问且已经存在栈中 balance=false;//拓扑失败 printf("存在回路，拓扑失败"); return; } if(!visited[w]){ DFS(G,w); } } printf(v);//输出顶点 isStack[v]=false;//每次出栈，都需要修改数组 }- 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
关键路径-边表示活动
AOE网：带权有向图中，顶点表示事件，有向边表示活动，边的权值表示完成活动的开销，这种用边表示活动的网络叫做AOE网
AOE的两个性质
1、只有在某个顶点所代表的事件发生后，各个顶点触发的各有向边所代表的活动才能开始
2、只有在进入某顶点的各有向边代表的活动都已经结束，该顶点表示的事件才能发生
另外有一些活动是可以并行进行的
在AOE中仅有一个入度为0的顶点表示为开始顶点(源点)，它表示整个工程的开始，也仅有一个出度为0的顶点，叫做结束顶点(汇点)，它表示整个工程的结束
关键路径：从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的称为关键路径，关键路径上的活动叫做关键活动
完成整个工程的最短时间就是关键路径长度，若关键路径活动不能按时完成，则整个工程的完成时间就会延长——有很重要的现实意义
事件Vk的最早发生事件ve(k)——决定了所有从Vk开始的活动能够开工的最早时间
事件Vk的最迟发生事件vl(k)——它是说在不推迟整个工程完成的前提下，该事件最迟必须发生的时间
时间余量：ve(k) - vl(k)，表示的是在不延后整个工程的前提下，活动k可以拖延的时间，如果一个活动的时间余量为0，说明这个活动必须如期完成，这个活动就是关键活动
- 求关键路径
-
求所有事件的最早发生时间
先求拓扑排序 1-3-2-5-4-6
源点的最早发生时间一定是0
后继结点的最早发生时间=前序结点的最早发生时间+对应的边的权值，取最大值(因为结点的所有前驱发生了它才能发生)
V1 V2 V3 V4 V5 V6 ve(k) 0 3 2 6 6 8 -
书上有一句话说求完ve的过程就可以知道关键路径，但是没有给具体解释，我对这句话的理解是，当我们在取这个最早发生时间的时候，对于多路径需要选择最早发生时间最大的那个值，我们在取这个最大的值的过程(这个最大值所经过的路径)，就是找关键路径的过程(就是关键路径)，这是有定义决定的，不理解的可以参考这个博文，过程写的十分详细
-
求所有事件的最迟发生时间
求逆拓扑排序 6-5-4-2-3-1
汇点最迟发生时间一定是它的最早发生时间
后继结点的最迟发生时间-对应边的权值，取最小值
V1 V2 V3 V4 V5 V6 vl(k) 0 4 2 6 7 8 -
所有活动的最早发生时间——和前向事件的最早发生时间是一样的
a1 a2 a3 a4 a5 a6 a7 a8 e(k) 0 0 3 3 2 2 6 6 -
所有活动的最迟发生时间——后继结点的最迟发生时间减去边的权值就是活动的最迟发生时间
a1 a2 a3 a4 a5 a6 a7 a8 l(k) 1 0 4 4 2 5 6 7 -
求所有活动的时间余量：活动最早 - 活动最晚
a1 a2 a3 a4 a5 a6 a7 a8 d(k) 1 0 1 1 0 3 0 1
d(k)=0，表示的关键活动，关键活动连成的边是关键路径。
关键活动时间被压缩，是可以缩短工程时间的，但是当关键活动被压缩到一定程度的时候，关键活动可能转化为非关键活动，这个时候关键路径已经改变。
关键路径可能不仅仅只有一条，这种特性下还是要缩短工程就要缩短所有关键路径的工程的时间。 -
相关阅读:
会声会影2022智能、快速、简单的视频剪辑软件
C语言结构体
指针强化与提高
洛谷P5764 新年好
【Invalid URL】The requested URL “[no URL]“, is invalid.
对话ACE第四期：分布式数据库未来发展的挑战和机遇
PB 变量命名规范
【项目实战】多租户实现数据库动态切换
恒运资本：存储市场有望触底反弹 电子竞技迎催化
SpringCLoud——Nacos注册中心
- 原文地址：https://blog.csdn.net/CodePlayMe/article/details/126905294
