南京公司网站设计定制,中国空间站是干什么的,seo外包服务,网页源代码下载音乐文章目录 题目方法一#xff1a;bfs方法二#xff1a;dfs 题目 这一题是在207题的基础上#xff0c;要统计拓扑排序的顺序集合#xff0c;所以只需要在207的基础上加入一个将拓扑排序的节点输出即可#xff08;有环无拓扑排序#xff09; 【LeetCode-中等题】207. 课程表… 文章目录 题目方法一bfs方法二dfs 题目 这一题是在207题的基础上要统计拓扑排序的顺序集合所以只需要在207的基础上加入一个将拓扑排序的节点输出即可有环无拓扑排序 【LeetCode-中等题】207. 课程表
方法一bfs
相比较207题 加入一个数组用于统计拓扑排序节点 其中拓扑排序的顺序就为队列的出队顺序
//方法一 bfs 广度优先public int[] findOrder(int numCourses, int[][] prerequisites) {int[] cou new int[numCourses];//课程号入度数组int[] num new int[numCourses];//用于存储拓扑排序ListListInteger couList new ArrayList();//课程号指向的课程号集合QueueInteger queue new LinkedList();//辅助队列 用于处理入度为0 的课程号for(int i 0 ;inumCourses ;i)//给集合中课程号初始化集合couList.add(new ArrayListInteger());for(int[] pre : prerequisites){cou[pre[0]];//统计各课程的入度couList.get(pre[1]).add(pre[0]);//给集合中课程号设置指向课程的集合}for(int i 0 ;inumCourses ;i){if(cou[i] 0) queue.offer(i);//搜索第一个入度为0 的课程号 加入队列}int i 0;//用于将拓扑排序加入到一个数组用的下标while(!queue.isEmpty()){int ids queue.poll();numCourses--;//取出一个元素 就让课程号总数-1num[i] ids;//拓扑排序 取出的元素加入到数组for(int cur : couList.get(ids)){// couList.get(ids) 根据课程号 取出课程号指向的课程 让被指向的课程号入度 -1if(cou[cur] 1 ) cou[cur]--;if(cou[cur] 0 ) queue.offer(cur);//若当前课程号入度为0 则加入队列}i;}if(numCourses 0) return num;else return new int[0];}方法二dfs
相比较207题 加入一个数组用于统计拓扑排序节点 其中使用一个栈来记录遍历完的节点 拓扑排序的顺序就为栈的出栈顺序
// 方法二 dfs 深度优先int[] cou null;// 设置全局变量 方便dfs使用int[] num null;ListListInteger couList null;boolean valid true;DequeInteger queue null;public int[] findOrder(int numCourses, int[][] prerequisites) {this.cou new int[numCourses];//课程号标记数组this.queue new LinkedList();//用于配合输出拓扑排序this.num new int[numCourses];//用于存储拓扑排序this.couList new ArrayList();//课程号指向的课程号集合for(int i 0 ;inumCourses ;i)//给集合中课程号初始化集合couList.add(new ArrayListInteger());for(int[] pre : prerequisites){couList.get(pre[1]).add(pre[0]);//给集合中课程号设置指向课程的集合}for(int i 0 ; inumCourses ;i){if(cou[i] 0) dfs(i);//课程号标记数组对应的值等于 0 开始递归}if(queue.size() ! numCourses) return new int[0]; //如果dfs完成之后 栈内元素个数不等于课程号总数 说明 拓扑排序不完整存在环自然不能将全部课程学习完else{//否则就代表无环 可以得到完整的拓扑排序for(int i 0 ; inumCourses ; i){num[i] queue.pop();//将压栈的课程号取出来 放到数组里面}} return num;}public void dfs(int i){cou[i] 1;for(int cur : couList.get(i)){if(cou[cur] 0){//课程号标记数组对应的值等于 0 继续递归dfs(cur);if(!valid) return ; //根据标记为判断是否有环 有环说明不能得到拓扑排序 直接返回 不往下面执行了}else if(cou[cur] 1){//如果搜索中存在环 将标志位设为fasle valid false;return;}}//一次遍历结束无环 就让该遍历元素位置的课程号数值置为 2 代表以该点进行dfs 无环cou[i] 2;queue.push(i); //让该dfs完的课程压栈 为什么要压栈 因为最后的拓扑排序就是栈的出栈顺序}
