【BFS专题】— 解决拓扑排序问题
拓扑排序介绍：
1、课程表 - 力扣（LeetCode）
思路：
- 通过Map<Integer, List<Integer>> 来创建邻接图，数组来表示入度
- 然后遍历课程数组，建图
- 然后再拓扑排序，bfs
- 最后在遍历入度数组，判断有没有环，即是不是入度都为零
- 代码：
class Solution {public boolean canFinish(int n, int[][] p) {//1、准备工作//统计每个顶点的如度int[] in = new int[n];//构造邻接图表Map<Integer, List<Integer>> edges = new HashMap<>();//2、建图for(int i = 0; i < p.length; i++){int a = p[i][0];int b = p[i][1];if(!edges.containsKey(b)){edges.put(b, new ArrayList<>());}edges.get(b).add(a);//入度加一in[a]++;}//3、拓扑排序//先把入度为零的点加入到对列中Queue<Integer> q = new LinkedList<>();for(int i = 0; i < n; i++){if(in[i] == 0){q.offer(i);}}//bfswhile(!q.isEmpty()){int t = q.poll();for(int a : edges.getOrDefault(t, new ArrayList<>())){in[a]--;if(in[a] == 0){q.offer(a);}}}//4、判断是否有环for(int x : in){if(x != 0){return false;}}return true;} }
2、课程表 II - 力扣（LeetCode）
思路：
- 和上一题一样，把最后出队的元素加入到数组中即可
- 代码：
public int[] findOrder(int n, int[][] p) {//准备工作List<List<Integer>> edges = new ArrayList<>();int[] in = new int[n];for(int i = 0; i < n; i++){edges.add(new ArrayList<>());}//建图for(int i = 0; i < p.length; i++){int a = p[i][0];int b = p[i][1];edges.get(b).add(a);in[a]++;}//拓扑排序//入度为0 的点入队Queue<Integer> q = new LinkedList<>();for(int i = 0; i < n; i++){if(in[i] == 0){q.add(i);}}//bfsint[] ret = new int[n];int index = 0;while(!q.isEmpty()){int t = q.poll();ret[index++] = t;for(int a : edges.get(t)){in[a]--;if(in[a] == 0){q.add(a);}}}//判断if(index == n){return ret;}else{return new int[0];}}
3、 火星词典 - 力扣（LeetCode）
思路：
- 拓扑排序
建图：用Map<Character, Set<Character>>
统计入度：Map<Character, Integer>- 细节问题：当第一组的字符串长度大于第二组的字符串时，不合法
- 代码：
class Solution {Map<Character, Set<Character>> edges = new HashMap<>();//邻接表Map<Character, Integer> in = new HashMap<>();//统计每个节点的入度boolean check;public String alienOrder(String[] words) {//1、初始化入度的哈希表和建邻接表for(String s : words){for(int i = 0; i < s.length(); i++){char ch = s.charAt(i);in.put(ch, 0);}}int n = words.length;for(int i = 0; i < n; i++){for(int j = i + 1; j < n; j++){add(words[i],words[j]);if(check == true){return "";}}}//2、拓扑排序Queue<Character> q = new LinkedList<>();//将入度为零的节点都入队for(char ch : in.keySet()){if(in.get(ch) == 0){q.offer(ch);}}StringBuffer ret = new StringBuffer();//遍历队列while(!q.isEmpty()){char t = q.poll();ret.append(t);if(!edges.containsKey(t)){continue;}for(char ch : edges.get(t)){in.put(ch, in.get(ch) - 1);if(in.get(ch) == 0){q.add(ch);}}}//3、判断，是否入度都是为零for(char ch : in.keySet()){if(in.get(ch) != 0){return "";}}return ret.toString();}//处理字符串public void add(String s1, String s2){int n = Math.min(s1.length(), s2.length());int i = 0;for( ; i < n; i++){char c1 = s1.charAt(i);char c2 = s2.charAt(i);if(c1 != c2){if(!edges.containsKey(c1)){edges.put(c1, new HashSet<>());}if(!edges.get(c1).contains(c2)){edges.get(c1).add(c2);in.put(c2, in.get(c2)+1);}break;}}if(i == s2.length() && i < s1.length()){check = true;}} }
