课程表 Ⅱ (medium)"/>
[拓扑排序]leetcode210:课程表 Ⅱ (medium)
题目:
题解:
- 拓扑排序,与207. 课程表代码一样的,只是将拓扑排序的顶点保留而已,注意边的数组给的是反向,这样的话,我们要将res反转就行了。
- 算法步骤:
- 1)遍历边的数组
prerequisites
建立图的邻接表
- 2)使用队列来存放入度为0的顶点,从而避免重复检测入度为0的顶点
- 3)删除入度为0的点,以及删除该点为起点的边,并统计删除入度为0的顶点个数
- 4)若有向图无环,则res.size()等于顶点数numCounses;否则有向图有环,则res.size()会小于顶点数numCounses
拓扑排序算法思路:
- 1)在有向图中选一个入度为0的顶点且输出之
- 2)从图中删除该顶点和所有以它为弧尾的弧
- 3)重复上述两步,直至全部顶点均已输出,或者当前图中不存在无前驱的顶点为止。=后者表示的是该有向图存在环。
代码如下:
// 2022/4/8 代码
vector<int> graph[2010];
class Solution {
public:// 对有向无环图进行拓扑排序vector<int> findOrder(int n, vector<vector<int>>& g) {//for(int i=0;i<n;++i)graph[i].resize(0);fill(graph, graph+2010, vector<int>());vector<int> res,indegrees(n);for(auto& edge:g){graph[edge[1]].push_back(edge[0]);indegrees[edge[0]]++;}queue<int> q;// 入度为0的顶点入队列for(int i=0;i<n;++i){if(!indegrees[i])q.push(i);}// 开始进行bfswhile(q.size()){auto i=q.front();q.pop();// 在res中添加拓扑序列的顶点res.push_back(i);// 删除 i->j 的所有邻接边for(int j:graph[i]){if(--indegrees[j]==0)q.push(j);}}return res.size()==n?res:vector<int> ();}
};
更多推荐
[拓扑排序]leetcode210:课程表 Ⅱ (medium)
发布评论