今天，小编带着大家来学习图中非常重要的一环，拓扑排序和关键路径！
目录
一. 绪论——实际应用
二. 拓扑排序
（一）.含义
（二）.实现原理
（三）.代码实现
三. 关键路径
（一）.含义
（二）.实现原理
（三）.代码实现
首先，我们需要知道的是，拓扑排序是关键路径的基础，正因如此，当我们知道了关键路径在生活中的应用，相信大家也就明白这两个算法的重要性了！
一. 绪论——实际应用
我们以实际生活为例，让大家了解关键路径的应用。
假设现在有一个工程，分为好多个步骤，每个步骤又需要不同的时间来完成，关键路径的作用就是让我们知道这个工程里有哪些步骤是不可替代的，会影响整个工期进行，而那些步骤即便慢一些也没关系，不会影响整个工期的。
二. 拓扑排序
（一）.含义
要了解拓扑排序的含义，我们首先要知道AOV网。AOV网就是不带权值的有向的不带环的网图。
什么是不带环？
上图理解！
而拓扑排序就是基于AOV网图实现的，大家不要感觉说AOV网图条件太苛刻了，实际上我们的很多工程都是AOV网图，只有实现一个步骤才能进行下一个步骤，例如学习就是就是一个AOV网，我们只有学过c语言后才能学数据结构，才能学数据库以及之后的内容。
拓扑排序就是把所有AOV网中的顶点都单次输出出来。
（二）.实现原理
拓扑排序是基于邻接表实现的。
实现拓扑排序，过程如下：
首先我们需要创建一个栈，用来装入度为0的顶点。
1.计算所有顶点的入度，入度为0的入栈
2.出栈一个顶点a，a的入度为0，把它保存在一个int类型数组topo里。
3.从a开始走到它的下一个顶点b，把b的入度减1，再找一个入度为0的顶点入栈。
4.重复步骤2和步骤3，直到所有的顶点都走过为止。
5.topo数组依次输出就是拓扑排序后的结果
还是那句话，上图理解！
（三）.代码实现
#define Maxvex 100
typedef char vextype;
typedef int undform;
typedef struct arcnode//边表
{
int arcnode;//此边节点对应顶点的下标
struct arcnode* nextarcnode;//下一个此根节点指向的边节点
int weight;//边的权值
}Arcnode;
typedef struct vexnode//节点表
{
vextype val;//节点值
Arcnode* Nextarc;//节点指向的第一个边
}Vexnode[Maxvex], onevexnode;
typedef struct Graph//图
{
Vexnode vexall;//所有的节点作为一个数组
int vexnum, arcnum;//节点，边的个数
}Graph;
bool ToPosort(Graph* gp, int * Topo)//拓扑排序
{
int* indegree = (int*)new int[gp->vexnum];//建立入度数组
memset(indegree, 0, sizeof(int) * gp->vexnum);
std::stack<int> st;//建立栈
for (int i = 0; i < gp->vexnum; i++)//计算所有顶点的入度
{
arcnode* node = gp->vexall[i].Nextarc;
while (node != NULL)
{
indegree[node->arcnode]++;
node = node->nextarcnode;
}
}
for (int i = 0; i < gp->vexnum; i++)//入度为0入栈
{
if (indegree[i] == 0)
{
st.push(i);
}
}
int size = 0;//判断多少个顶点无环
int topo_i = 0;
while (!st.empty())
{
int i = st.top();
st.pop();
Topo[topo_i++] = i;//顶点入拓扑序列
size++;
arcnode* node = gp->vexall[i].Nextarc;
while (node != NULL)
{
--indegree[node->arcnode];
if (indegree[node->arcnode] == 0)
{
st.push(node->arcnode);
}
node = node->nextarcnode;
}
}
if (size == gp->vexnum) return true;
else return false;
}三. 关键路径
（一）.含义
小编想了好久，决定还是用实例来给大家解释关键路径到底是个什么东西。相信大家看完就能完全理解了！
假设现在有一个工程，分为好多个步骤，每个步骤又需要不同的时间来完成，我们可以用一个带权有向无环图——AOE网来表示，顶点代表步骤，边的权值代表步骤1开始执行到下一步将要开始所需时间。
图来表示就是这样：
例图的意思就是从以顶点1代表的起始步骤到以顶点9代表的终点步骤，该工程可以经过这里头的某些顶点步骤来完成。
由图可知该工程可以经历的路径共有4条，分别是：
①1->2->3->6->8->9 完工时间:1+2+2+4+2=11h
②1->4->5->6->7->9 完工时间:1+1+1+3+1=7h
③1->2->3->6->7->9 完工时间:1+2+2+3+1=9h
④1->4->5->6>8->9 完工时间:1+1+1+4+2=9h
而但每条路径从开工到完成所需的时间是不同的，该工程最短7h完成，最长11h完成，而关键路径就是用来算我们确保工程一定能完成的情况下，该步骤时间的改变一定会影响总工期的时间。
什么意思？
我们以该图为例，最长时间11h就是该工程一定能完成的时间，因为在11h内该工程不管采用那条路径都能完成。
1->2->3->6->8->9就是这里边的关键路径，因为这里边的每一个步骤都没有余量时间，而没有余量时间的步骤就是改变该步骤时间就一定会影响工期的步骤。
余量时间：我们拿3和5步骤为例，3到6是2h，5到6是1h，这说明5到6与3到6相比有1小时的空余，这就是余量时间。3就是没有余量时间，而5就是有余量时间。
关键路径就是这些没有余量时间的步骤所连起来的一条通路。
（二）.实现原理
关键路径的实现是基于拓扑排序的。
其次，我们还需要一个int类型数组etv来存放顶点的最早发生时间， int类型数组ltv来存放顶点的最晚发生时间。小编看来看，我们要是想学好关键路径，必须要彻底清楚什么是最早最晚发生时间。
最早发生时间：该顶点在允许的时间范围内，最早进入下一顶点的时间。
最晚发生时间：该顶点在允许的时间范围内，最晚进入下一顶点的时间。
举个例子：
以该图为例，关键路径是a->c->e->f，所以对于b->d而言有两种选择：
一是早早完成，歇着，这是最早发生时间，值是1，因为a->b需要1小时；
二是先歇着，等到能和c->e一起完成时再开始，这是最晚发生时间，值是2，因为是a->b加歇的1小时。
我们用拓扑序列topo数组从头开始依次算每个顶点的最早发生时间，因为topo数组是按从图头开始依次存放直到图尾，刚好符合顶点依次发生，所需时间是之前顶点时间的迭代。
再从拓扑序列尾开始往前走，依次计算最晚发生时间，以d点为例，最晚发生时间就是f的最晚时间减d->f的时间，即5-1=4。
所有顶点都算完etv与ltv后，遍历每个顶点，如果一个顶点的最早发生时间etv等于最晚发生ltv时间，那它就是关键路径的顶点。
最后，打印每个关键路径的顶点到下一个关键路径顶点即可。文章来源：https://www.toymoban.com/news/detail-412966.html
（三）.代码实现
void CriticalPath(Graph* gp)//关键路径
{
cout << "****************CriticalPath*******************\n";
int* topo = (int*)new int[gp->vexnum];
if (!ToPosort(gp, topo))//判断是否带环
{
cout << "非AOE图！";
return;
}
int* etv = (int*)new int[gp->vexnum];//顶点最早发生时间
int* ltv = (int*)new int[gp->vexnum];//顶点最晚发生时间
for (int i = 0; i < gp->vexnum; i++)//初始化etv
{
etv[i] = 0;
}
for (int i = 0; i < gp->vexnum; i++)//建立最早时间etv
{
arcnode* node = gp->vexall[topo[i]].Nextarc;//拓扑序列中该顶点的第一条边,下标是拓扑序列值，即topo[i]作为下标！
while (node != NULL)
{
if (etv[node->arcnode] < etv[topo[i]] + node->weight)
//存最早时间，但是最早时间定义是确保事件一定能发生，要想一定能发生，那么就该取时间最长的路径，这就是最早发生时间
etv[node->arcnode] = etv[topo[i]] + node->weight;
node = node->nextarcnode;
}
}
for (int i = 0; i < gp->vexnum; i++)//初始化最晚发生时间
{
ltv[i] = etv[topo[gp->vexnum - 1]];//注意！这里是用topo序列的值来作为下标的，拓扑序列的尾才是图的尾
}
for (int i = gp->vexnum - 1; i >= 0; i--)//建立最晚时间ltv
{
arcnode* node = gp->vexall[topo[i]].Nextarc;//从拓扑序列尾端开始,所以用topo[i]来作为下标！
while (node != NULL)
{
if (ltv[topo[i]] > ltv[node->arcnode] - node->weight)
// 节点顺序关系： i -> node
ltv[topo[i]] = ltv[node->arcnode] - node->weight;
node = node->nextarcnode;
}
}
for (int i = 0; i < gp->vexnum; i++)//判断关键路径并打印
{
arcnode* node = gp->vexall[i].Nextarc;
while (node != NULL)
{
if (ltv[node->arcnode] == etv[i] + node->weight)//注意要用最早发生时间加权值来与最晚发生时间相比
cout << gp->vexall[i].val << "->" << gp->vexall[node->arcnode].val << endl;
node = node->nextarcnode;
}
}
}创作不易，恳求点赞支持😆 如有错误，敬请斧正文章来源地址https://www.toymoban.com/news/detail-412966.html
到了这里，关于超详细讲解实现拓扑排序、关键路径的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
