使用拓扑排序解决力扣课程表问题

"力扣500题刷题笔记10" 在编程竞赛平台LeetCode上，有一类问题涉及到课程选择的优化，这类问题通常可以用拓扑排序算法来解决。拓扑排序是一种对有向无环图（DAG，Directed Acyclic Graph）进行排序的方法，它将图中的所有顶点排列成一个线性序列，使得对于图中任意一对节点u和v，如果存在从u到v的边<u, v>，那么u总是在v之前。 在题目描述的示例中，有两门课程（编号为0和1），课程0是课程1的先修课程。如果给定的先修课程关系形成一个环，那么就无法进行拓扑排序，因为环意味着总会有一个课程依赖于它自己或另一个在环内的课程，从而无法形成一个没有前置课程的起始点。例如，如果课程0和1互相依赖（即[0,1]和[1,0]），那么不存在合法的选课顺序，返回false。 拓扑排序的基本步骤如下： 1. 建立图：根据先修课程关系，构建一个有向图。每个课程作为一个节点，每条边表示课程间的依赖关系。 2. 计算入度：记录每个节点的入度，即指向该节点的边的数量。入度为0的节点表示没有依赖关系，可以作为排序的起始点。 3. 初始化队列：将所有入度为0的节点放入队列。 4. 拓扑排序：从队列中取出一个节点now，将其添加到拓扑序列中，并遍历其所有邻接点nxt，将nxt的入度减1。如果nxt的入度变为0，将其加入队列。 5. 重复步骤4，直到队列为空。 6. 检查结果：如果拓扑序列的长度等于图中节点的数量，说明图中没有环，可以进行拓扑排序，返回true。否则，存在环，返回false。 在实现拓扑排序的代码中，通常会用到数据结构如队列（用于处理入度为0的节点）和哈希表（用于存储节点的邻接列表以及记录每个节点的入度）。时间复杂度为O(V+E)，其中V是节点数量，E是边的数量，因为需要遍历所有的节点和边。 对于C++的实现，可能会包含以下关键部分： ```cpp vector<int> topologicalSort(vector<vector<int>>& prerequisites, int numCourses) { vector<vector<int>> graph(numCourses); // 用于存储邻接列表 vector<int> inDegree(numCourses, 0); // 存储入度 queue<int> q; // 用于存储入度为0的节点 // 建图 for (auto& pair : prerequisites) { graph[pair[1]].push_back(pair[0]); ++inDegree[pair[0]]; } // 将入度为0的节点放入队列 for (int i = 0; i < numCourses; ++i) { if (inDegree[i] == 0) { q.push(i); } } vector<int> result; while (!q.empty()) { int now = q.front(); q.pop(); result.push_back(now); // 更新邻接点的入度 for (int nxt : graph[now]) { --inDegree[nxt]; if (inDegree[nxt] == 0) { q.push(nxt); } } } // 如果拓扑序列的长度等于节点数，返回true，否则返回false return result.size() == numCourses ? result : vector<int>(); } ``` 这个算法的核心在于通过队列处理没有前置课程的节点，并在每次访问完一个节点后更新邻接节点的入度。如果在处理过程中发现队列为空但仍有节点未被处理，或者在拓扑序列中找到环，就表明图中存在环，无法进行有效的拓扑排序。