BFS 解决拓扑排序

1.课程表

1.1. 题⽬链接：

https://leetcode.cn/problems/course-schedule

1.2 题⽬描述：

1.3. 解法：

算法思路： 原问题可以转换成⼀个拓扑排序问题。 ⽤ BFS 解决拓扑排序即可。 拓扑排序流程：

a. 将所有⼊度为 0 的点加⼊到队列中；

b. 当队列不空的时候，⼀直循环：

i. 取出队头元素；

ii. 将于队头元素相连的顶点的⼊度 - 1；

iii. 然后判断是否减成 0,。如果减成 0，就加⼊到队列中。

1.4 代码

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], b = p[i][1]; // b -> aif(!edges.containsKey(b)){edges.put(b, new ArrayList<>());}edges.get(b).add(a);in[a]++;}// 3. 拓扑排序 Queue<Integer> q = new LinkedList<>();// (1) 先把⼊度为 0 的点，加⼊到队列中 for(int i = 0; i < n; i++){if(in[i] == 0) q.add(i);}// (2) bfswhile(!q.isEmpty()){int t = q.poll();for(int a : edges.getOrDefault(t, new ArrayList<>())){in[a]--;if(in[a] == 0) q.add(a);}}// 4. 判断是否有环 for(int x : in)if(x != 0) return false;return true;}
}

2. 课程表

2.1题⽬链接：

https://leetcode.cn/problems/course-schedule-ii

2.2 题⽬描述：

2.3解法：

算法思路： 原问题可以转换成⼀个拓扑排序问题。 ⽤ BFS 解决拓扑排序即可。 拓扑排序流程：

a. 将所有⼊度为 0 的点加⼊到队列中；

b. 当队列不空的时候，⼀直循环：

i. 取出队头元素；

ii. 将于队头元素相连的顶点的⼊度 - 1；

iii. 然后判断是否减成 0,。如果减成 0，就加⼊到队列中。

2.4代码

class Solution 
{public int[] findOrder(int n, int[][] prerequisites) {// 1. 准备⼯作 int[] in = new int[n]; // 统计每个顶点的⼊度 List<List<Integer>> edges = new ArrayList<>();for(int i = 0; i < n; i++){edges.add(new ArrayList<>());}// 2. 建图 for(int i = 0; i < prerequisites.length; i++){int a = prerequisites[i][0], b = prerequisites[i][1]; // b -> aedges.get(b).add(a);in[a]++;}// 3. 拓扑排序 Queue<Integer> q = new LinkedList<>();int[] ret = new int[n];int index = 0;for(int i = 0; i < n; i++){if(in[i] == 0) q.add(i);}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;return new int[0];}
}

3. ⽕星词典（hard）

3.1题⽬链接：

https://leetcode.cn/problems/Jf1JuT

3.2 题⽬描述：

3.3 解法：

算法思路： 将题意搞清楚之后，这道题就变成了判断有向图时候有环，可以⽤拓扑排序解决。 如何搜集信息（如何建图）：

a. 两层 for 循环枚举出所有的两个字符串的组合；

b. 然后利⽤指针，根据字典序规则找出信息。

3.4代码

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.add(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), c2 = s2.charAt(i);if(c1 != c2){// c1 -> c2if(!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;}
}