算法 之 拓 扑 排 序

拓扑排序

• 拓扑排序，常用于这个课程表安排类型的，对于一个抽象为一个有向无环图，经过排序之后，排序之后的元素x,y，仍然保持着在原来的有向无环图当中，x->y，也就是前后的顺序仍然不变

灵神讲解

• 讲一下拓扑排序的思路：
  • 首先输入的是一个边的关系edges[i] = [x,y]表示，存在x->y的有向边，我们需要将这个边，使用邻接表存储起来，同时还使用一个数组存储每一个顶点的入度数量
  • 使用一个队列来存储候选将要拓展的节点，当然一开始，加入队列的元素就是入度为0的节点
  • 选取队列中的元素，加入最终的排序的数组中，同时，对于以该元素作为起始节点的边所对应的节点的入度数量应该-1，同时判断，将新的入度数量为0的节点加入候选队列当中
  • 如果最终，排序的元素数量少于总的节点数量，则说明存在环

// 返回有向无环图（DAG）的其中一个拓扑序
// 如果图中有环，返回空列表
// 节点编号从 0 到 n-1
vector<int> topologicalSort(int n, vector<vector<int>>& edges) {vector<vector<int>> g(n);vector<int> in_deg(n);for (auto& e : edges) {int x = e[0], y = e[1];g[x].push_back(y);in_deg[y]++; // 统计 y 的先修课数量}queue<int> q;for (int i = 0; i < n; i++) {if (in_deg[i] == 0) { // 没有先修课，可以直接上q.push(i); // 加入学习队列}}vector<int> topo_order;while (!q.empty()) {int x = q.front();q.pop();topo_order.push_back(x);for (int y : g[x]) {in_deg[y]--; // 修完 x 后，y 的先修课数量减一if (in_deg[y] == 0) { // y 的先修课全部上完q.push(y); // 加入学习队列}}}if (topo_order.size() < n) { // 图中有环return {};}return topo_order;
}

拓扑排序+dp解决工程完成时间

• 拓扑排序，适合处理有向无环图当中，解决活动先后顺序的安排，当然，我们也可以计算出完成全部的活动所需的最少时间
• 我们定义dp[i]为完成任务i的最早完成时间，那么就有递推公式dp[i] = max(dp[j) +time[i]，其中dp[j]为j->i的节点

2050.并行课程 III

• 思路分析：
  • 解决的方法，也就是在出候选队列的时候，我们在更新入度节点的时候，同时更新这个dp[i]即可

class Solution {
public:int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {// 拓扑排序+dpvector<int> dp(n+1);vector<int> ine(n+1);vector<vector<int>> e(n+1);queue<int> q;for (auto p : relations){int u = p[0],v = p[1];e[u].push_back(v);ine[v]++;}// 初始化队列for (int i = 1; i <= n; i++){if (ine[i] == 0){q.push(i);dp[i] = time[i-1];}}// 开始排序while (q.size()){int x = q.front();q.pop();for (auto c : e[x]){ine[c]--;dp[c] = max(dp[c],dp[x] + time[c-1]);if (ine[c] == 0){q.push(c);}}}// 遍历完，找到这个最大的dpint ans = 0;for (int i = 1;i <= n; i++){cout << dp[i] << " ";ans = max(ans,dp[i]);}return ans;}
};