BFS 算法专题（五）：BFS 解决拓扑排序
目录
1. 拓扑排序简介
1.1 有向无环图 (DAG 图)
1.2 AOV 网(顶点活动图)
1.3 拓扑排序
1.3.1 如何实现
2. 力扣实战应用
2.1 课程表
2.1.1 算法原理
2.1.2 算法代码
2.2 课程表 II
2.2.1 算法原理
2.2.2 算法代码
2.3 火星词典 (hard) (原剑指offer)
2.3.1 算法原理
2.3.2 算法代码
1. 拓扑排序简介
1.1 有向无环图 (DAG 图)
顶点与顶点之间的边, 是具有方向, 并且不会构成环(无回路).
有向图中, 有两个重要概念:
- 出度
- 入度
1.2 AOV 网(顶点活动图)
在有向无环图中, 用顶点来表示一个活动, 用边来表示活动的先后顺序的图结构.
1.3 拓扑排序
找到做的事情(活动)的先后顺序(可能不是唯一的).
排序过程:
- 找到入度为 1 的点
- 删除与该点连接的边
- 重复 1, 2 操作, 直至图中没有点或者没有入度为 0 的点(可能存在环)
重要应用: 判断有向图中是否有环
1.3.1 如何实现
借助队列, 进行一次 BFS:
初始化: 把所有入度为 0 的点加入到队列中
当队列不为空时:
- 拿出队头元素, 加入已排序序列
- 删除与该元素相连接的边
- 判断: 与删除边相连的点, 是否入度为 0 , 若是, 则加入队列中
2. 力扣实战应用
2.1 课程表
. - 力扣（LeetCode）
2.1.1 算法原理
问题核心: 判断 "图" 中是否带环 => 拓扑排序
灵活使用 Java 提供的集合类, 进行图的构建:
- 构建邻接表 => 1. List<List<Integer>> 2. Map<Integer, List<Integer>>
借助队列, 进行 BFS , 判断是否带环:
- 将所有入度为 0 的节点入队(从图中拿走该节点)
- 拿出队头元素, 删除与该元素相邻的边
- 判断与删除的边相连的节点入度是否为 0
- 若为 0 , 则入队
- 重复以上操作
- 当队空时, 若还有入度不为 0 的节点, 则说明该图带环
注意: 使用数组记录各节点的入度 => int[] in
2.1.2 算法代码
class Solution {public boolean canFinish(int n, int[][] p) {// 记录节点的入度int[] in = new int[n];// 构建邻接表Map<Integer, List<Integer>> edges = new HashMap<>();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]++;}Queue<Integer> q = new LinkedList<>();// 将入度为 0 的节点入队for(int i = 0; i < n; i++) {if(in[i] == 0) q.offer(i);}// bfswhile(!q.isEmpty()) {int t = q.poll();for(int x : edges.getOrDefault(t, new ArrayList<>())) {in[x]--;if(in[x] == 0) q.offer(x);}}for(int x : in) {if(x != 0) return false;}return true;}
}2.2 课程表 II
. - 力扣（LeetCode）
2.2.1 算法原理
本题解法与上题解法一致, 唯一需要多处理的就是记录拓扑排序的序列.
2.2.2 算法代码
class Solution {public int[] findOrder(int n, int[][] p) {// 统计节点的入度情况int[] in = new int[n + 1];// 创建邻接表Map<Integer, List<Integer>> edges = new HashMap<>();for(int i = 0; i < p.length; i++) {int a = p[i][0], b = p[i][1]; // b -> ain[a]++;if(!edges.containsKey(b)) {edges.put(b, new ArrayList<>());}edges.get(b).add(a);}Queue<Integer> q = new LinkedList<>();// 将入度为 0 的节点入队for(int i = 0; i < n; i++) {if(in[i] == 0) q.offer(i);}int size = 0;int[] ret = new int[n];// bfswhile(!q.isEmpty()) {int t = q.poll();// 进入拓扑序列ret[size++] = t;for(int x : edges.getOrDefault(t, new ArrayList<>())) {in[x]--;if(in[x] == 0) q.offer(x);}}return size == n ? ret : new int[]{};}
}2.3 火星词典 (hard) (原剑指offer)
. - 力扣（LeetCode）
2.3.1 算法原理
-
统计节点的入度信息 => Map<Character, Integer> ; 将每个节点的入度信息初始化为 0
-
构建邻接表 => Map<Character, Set<Character>> ; 注意不能重复接入存在的元素(所以使用 HashSet, 查找速度快)
-
搜集顺序信息 => 两层 for 循环 + 前后指针
-
细节问题 => "abc" "ab" , 这种特殊情况不合法, return "";
2.3.2 算法代码
class Solution {public String alienOrder(String[] words) {// 统计每个字符的入度Map<Character, Integer> in = new HashMap<>();for(String s : words) {for(int i = 0; i < s.length(); i++) {char ch = s.charAt(i);if(!in.containsKey(ch)) in.put(ch, 0);}}// 构建邻接表Map<Character, Set<Character>> edges = new HashMap<>();for(int i = 0; i < words.length; i++) {for(int j = i + 1; j < words.length; j++) {int front = 0, tail = 0;String s1 = words[i], s2 = words[j];while(front < s1.length() && tail < s2.length()) {char ch1 = s1.charAt(front), ch2 = s2.charAt(tail);if(ch1 == ch2) {front++;tail++;}else {// ch1 -> ch2// 可能重复存在 : ch1 -> ch2if(edges.containsKey(ch1) && edges.get(ch1).contains(ch2)) {break;} if(!edges.containsKey(ch1)) {edges.put(ch1, new HashSet<>());}// 入度加一in.put(ch2, in.get(ch2) + 1);// 放入邻接表edges.get(ch1).add(ch2);break;}}// 字符串不合法if(front < s1.length() && tail >= s2.length()) return ""; }}Queue<Character> q = new LinkedList<>();StringBuilder stringBuilder = new StringBuilder();// 将入度为 0 的节点入队for(Map.Entry<Character, Integer> e : in.entrySet()) {if(e.getValue() == 0) q.offer(e.getKey());}// bfswhile(!q.isEmpty()) {char ch = q.poll();stringBuilder.append(ch);Set<Character> set = edges.getOrDefault(ch, new HashSet<>());for(Character x : set) {in.put(x, in.get(x) - 1);if(in.get(x) == 0) q.offer(x);}}for(Map.Entry<Character, Integer> e : in.entrySet()) {if(e.getValue() != 0) return "";}return stringBuilder.toString();}
}END