算法题目---BFS解决拓扑排序

(一).概念关于“拓扑排序”主要看图片中的内容来理解。(二).具体题目1.课程表207. 课程表 - 力扣LeetCode解法拓扑排序class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { //1.准备工作 int[] inArrnew int[numCourses]; //统计入度 HashMapInteger, ListInteger hashMapnew HashMap(); //使用邻接表存图 //2.建图 for (int i 0; i prerequisites.length; i) { int aprerequisites[i][0]; int bprerequisites[i][1]; if (!hashMap.containsKey(b)){ hashMap.put(b,new ArrayList()); } hashMap.get(b).add(a); inArr[a]; } //3.拓扑排序 QueueInteger queuenew ArrayDeque(); //(1).将所有入度为0的点放入到队列中 for (int i 0; i numCourses; i) { if (inArr[i]0){ queue.add(i); } } //(2).进行bfs while (!queue.isEmpty()){ Integer poll queue.poll(); ListInteger list hashMap.getOrDefault(poll,new ArrayList()); for(int x:list){ //减少入度 inArr[x]--; if (inArr[x]0){ //将入度为0的点加入到队列中 queue.add(x); } } } //4.判断是否有环 for (int i 0; i numCourses; i) { if (inArr[i]!0){ return false; } } return true; } }2.课程表Ⅱ210. 课程表 II - 力扣LeetCode解法拓扑排序class Solution { public int[] findOrder(int numCourses, int[][] prerequisites) { //1.准备工作 int[] retnew int[numCourses]; int pos0; //标记结果数组的位置 int[] inArrnew int[numCourses]; //统计每个节点的入度 HashMapInteger,ListInteger hashMapnew HashMap(); //使用邻接表来存储图 //2.建图 for (int i 0; i prerequisites.length; i) { int aprerequisites[i][0]; int bprerequisites[i][1]; if (!hashMap.containsKey(b)){ hashMap.put(b,new ArrayList()); } hashMap.get(b).add(a); inArr[a]; } //3.拓扑排序 QueueInteger queuenew ArrayDeque(); for (int i 0; i inArr.length; i) { if (inArr[i]0){ queue.add(i); } } //4.bfs while (!queue.isEmpty()){ Integer poll queue.poll();//相当于从“图谱排序”中找到了一个点 ret[pos]poll; //将这个点添加到数组中因为但是是从队列中取出来的那么说明这个点的入度一定为0了 ListInteger list hashMap.getOrDefault(poll,new ArrayList()); for(int x:list){ inArr[x]--; if (inArr[x]0){ queue.add(x); } } } if (posnumCourses){ //如果最后的pos和numCourses相等那么说明所有的值都存在ret中了 return ret; }else{ return new int[0]; } } }3.火星词典LCR 114. 火星词典 - 力扣LeetCode解法拓扑排序class Solution { HashMapCharacter, HashSetCharacter hashMapnew HashMapCharacter, HashSetCharacter(); //建图使用的哈希表 HashMapCharacter,Integer innew HashMap(); //统计入度信息 boolean check; public String alienOrder(String[] words) { for(String str:words){ for (int i 0; i str.length(); i) { in.put(str.charAt(i),0); } } for (int i 0; i words.length; i) { for (int j i1; j words.length; j) { add(words[i],words[j]); if (checktrue){ return ; //特殊情况 } } } QueueCharacter queuenew ArrayDeque(); for (char ch:in.keySet()){ if (in.get(ch)0){ queue.add(ch); } } StringBuilder stringBuildernew StringBuilder(); while (!queue.isEmpty()){ Character poll queue.poll(); stringBuilder.append(poll); if (!hashMap.containsKey(poll)){ continue; //如果不存在哈希表中说明没有顺序关系此时直接跳过这次循环即可 } for(char ch:hashMap.get(poll)){ in.put(ch,in.get(ch)-1); if (in.get(ch)0){ queue.add(ch); } } } for(char ch:in.keySet()){ if (in.get(ch)!0){ return ; } } return stringBuilder.toString(); } private void add(String s1, String s2) { int lenMath.min(s1.length(),s2.length()); int i 0; for (; i len; i) { char c1s1.charAt(i); char c2s2.charAt(i); if (c1!c2){ if (!hashMap.containsKey(c1)){ hashMap.put(c1,new HashSet()); } if (!hashMap.get(c1).contains(c2)){ hashMap.get(c1).add(c2); in.put(c2,in.get(c2)1); } break; } } if (is2.length() is1.length()){ checktrue; } } }