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 -> a

 if(!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) bfs

 while(!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 -> a

 edges.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 -> 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;
 }
}