AOV网：在DAG中，用顶点表示活动，用弧表示活动之间的优先关系的有向图称为顶点表示活动的网---->工程中小项目次序
AOE网：在DAG中，用顶点表示事件，用带权有向边表示活动，边权表示活动持续时间
---->工程中小项目次序，每个小项目多久做完，整个工程多久做完
事件：刹那间发生的一件事情
活动：一个完整流程，可能由很多事件组成，有开始和结束
关键路径：整个项目工程中，耗时最长的路径称为关键路径，关键路径上的活动称为关键活动。---->注：关键路径不唯一，我们需要关注所有关键路径
关键路径：从起点到终点，最长的路径（们），由关键活动组成。
关键活动：最早开始时间 == 最晚开始时间 ETE == LTE
非关键活动：最早开始时间 != 最晚开始时间 ETE != LTE
（1）事件最早发生时间（ETV）
1.起点事件start最早发生时间 == 0 ETV[start] == 0
2.其余事件的最早发生时间基于拓扑序列去算
ETV[j] = max(ETV[j],ETV[i]+wi) i------>j
（2）事件最晚发生时间（LTV）
1.终点事件end的最晚发生时间 LTV[end] = ETV[end] (若未给出的话则按左式计算)
2.其余事件最晚发生时间基于逆拓扑序列计算
LTV[i] = min(LTV[i],LTV[j]-wj) i------>j
3.起点事件start最晚发生时间 == 0 LTV[start] == 0 == ETV[start]
（3）活动最早开始时间（ETE/ES）
1.ETE==该边起点事件的ETV
ETE = ETV[i]
（4）活动最晚开始时间（LTE/LS）
注：保证终点事件在DDL之前按时发生
1.LTE==该边终点事件LTV - 该边权值
注：终点事件最早发生时间就是工程完成时间
时间复杂度：O(n+m)
注：n为点数，m为边数
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
//引入一个栈，用于保存所有入度为零的的点的下标
class Stack_Node
{
public:
int data;
Stack_Node* next;
};
class m_stack
{
public:
Stack_Node* head;
public:
m_stack()
{
head = new Stack_Node;
if (head == nullptr)
{
cout << "开辟失败" << endl;
}
else
{
head->next = nullptr;
}
}
void m_push(int k)
{
Stack_Node* p = new Stack_Node;
p->data = k;
p->next = head->next;
head->next = p;
}
int m_pop()
{
if (head->next == nullptr)
{
cout << "栈空" << endl;
return -1;
}
Stack_Node* p = head->next;
int ret = p->data;
head->next = p->next;
delete p;
p = nullptr;
return ret;
}
};
class List_Node
{
public:
int data;
int wi;//权值
List_Node* next;
};
class Graph_Node
{
public:
char vi;
List_Node* first;
};
class Graph
{
public:
int size1;//点的个数
int size2;//边的个数
Graph_Node* g;//邻接表
int* ind;//入度数组
int* topo;//拓扑序列,改为记录下标便于计算
int* etv;//事件最早发生时间
int* ltv;//事件最晚发生时间
public:
Graph(int sz1,int sz2):size1(sz1),size2(sz2)
{
g = new Graph_Node[sz1];
ind = new int[sz1];
topo = new int[sz1];
etv = new int[sz1];
ltv = new int[sz1];
if (g == nullptr ||
ind == nullptr ||
topo == nullptr||
etv == nullptr ||
ltv == nullptr)
{
cout << "开辟失败" << endl;
}
else
{
//初始化点
for (int i = 0; i < sz1; ++i)
{
cin >> g[i].vi;
g[i].first = nullptr;
ind[i] = 0;
topo[i] = 0;
etv[i] = 0;
}
//输入边
char x(0);
char y(0);
int xi(0);
int yi(0);
int w(0);
for (int i = 0; i < sz2; ++i)
{
cin >> x >> y >> w;
xi = find(x);
yi = find(y);
//y为x邻接点
List_Node* s = new List_Node;
s->data = yi;
s->wi = w;
//进行头插
s->next = g[xi].first;
g[xi].first = s;
//统计y入度
ind[yi]++;
}
}
}
int find(char k)
{
for (int i = 0; i < size1; ++i)
{
if (g[i].vi == k)
{
return i;
}
}
return -1;
}
bool topo_sort()
{
bool flag(false);//判断能否找到拓扑序列
//引入一个栈，用于保存所有入度为零的的点的下标
m_stack s;
for (int i = 0; i < size1; ++i)
{
if (ind[i] == 0)
{
s.m_push(i);
}
}
int v_i(0);//出栈点的下标
//j为topo数组下标
for (int i = 0, j = 0; i < size1; ++i, ++j)
{
v_i = s.m_pop();
if (v_i == -1)
{
flag = false;//找不到拓扑序列
break;
}
//删除（并没有真正删除，只是入度减一）
topo[j] = v_i;
List_Node* p = g[v_i].first;
int a(0);//存储邻接点下标
while (p != nullptr) //v_i------>a
{
a = p->data;
ind[a]--;
//更新v_i邻接点etv
if (etv[a] < etv[v_i] + p->wi)
{
etv[a] = etv[v_i] + p->wi;
}
if (ind[a] == 0)
{
s.m_push(a);
}
p = p->next;
}
if (i == size1 - 1)
{
flag = true;
}
}
if (flag == false)
{
cout << "该图带环，无拓扑序列" << endl;
return flag;
}
else
{
cout << "该图拓扑序列为：" << endl;
for (int i = 0; i < size1; ++i)
{
cout << topo[i] << ' ';
}
cout << endl;
return flag;
}
}
void Critical_Path()
{
//end为结束事件下标
int end(topo[size1 - 1]);
//初始化ltv
for (int i = 0; i < size2; ++i)
{
ltv[i] = etv[end];
}
//基于逆拓扑序列更新ltv
//求x的ltv
int x(0);
for (int i = size1 - 2; i >= 0; --i)
{
x = topo[i];
//遍历x出边单链表
List_Node* p = g[x].first;
//存储邻接点下标
int a(0);
while (p != nullptr)
{
a = p->data; //x------->a
if (ltv[x] > ltv[a] - p->wi)
{
ltv[x] = ltv[a] - p->wi;
}
p = p->next;
}
}
cout << "以下是关键活动" << endl;
//遍历所有边，求每个边的ete，lte
//k为终点,i为起点
int k(0);
int ete(0);
int lte(0);
for (int i = 0; i < size1; ++i)
{
for (List_Node* p = g[i].first; p != nullptr; p = p->next)
{
k = p->data;
ete = etv[i];
lte = ltv[k] - p->wi;
if (ete == lte)
{
cout << g[i].vi << ' ' << g[k].vi << endl;
}
}
}
}
};
int main()
{
Graph g(9, 11);
g.topo_sort();
g.Critical_Path();
return 0;
}
/*
9 11
A B C D E F G H I
A B 6
A C 4
A D 5
B E 1
C E 1
D F 2
E G 9
E H 7
F H 4
G I 2
H I 4
*/
