【数据结构与算法】拓扑排序,关键活动,关键路径 详解

拓扑排序算法

bool topologicalSort() {
	stack<int> stk;
	int id[N];
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (!inDeg[i]) {
			stk.push(i);
		}
		id[i] = inDeg[i];
	}
	while (stk.size()) {
		int t = stk.top();
		stk.pop();
		cout << t << " ";
		cnt++;
		for (auto i : g[t]) {
			id[i]--;
			if (!id[i]) {
				stk.push(i);
			}
		}
	}
	cout << endl;
	return cnt == n;
}

举例简述"拓扑排序"所解决的实际问题。

拓扑排序在很多实际问题中都有应用，其中一个常见的例子是任务调度问题。

假设有一系列的任务需要完成，而这些任务之间存在一定的依赖关系，即某些任务必须在其他任务完成后才能开始。你的目标是找到一种完成任务的顺序，使得每个任务在其依赖的任务完成后才开始。

任务可以看作是图的节点，任务之间的依赖关系可以看作是有向边。拓扑排序就是找到一种节点的排列顺序，使得每个节点（任务）都在其有向边指向的节点（依赖的任务）之后。

通过拓扑排序，可以得到一个满足所有依赖关系的任务完成顺序。如果无法找到这样的顺序，那么说明任务之间的依赖关系存在环，也就是说存在无法完成的任务。

请图示”拓扑排序”的过程。

什么是关键活动？

l(j)＝e(j)的活动(活动的最迟开始时间 = 活动的最早开始时间)，即关键路径上的所有活动。

什么是关键路径？

从源点到收点的最长的一条路径，或者全部由关键活动构成的路径。

举例简述"关键路径"所解决的实际问题。

可用于估算工程项目完成时间。