💕"请努力活下去"💕
作者：Lvzi
文章主要内容：算法系列–算法系列–BFS解决拓扑排序

大家好,今天为大家带来的是算法系列--BFS解决拓扑排序

前言:什么是拓扑排序
拓扑排序–解决有顺序的排序问题(要做事情的先后顺序)

几个基本概念

1. 有向无环图:有方向,但是不存在环路
2. 入度:有多少条路可以走到当前节点
3. 出度:从当前节点出发,有多少条线路

拓扑排序问题的思路比较固定,难点在于灵活的采用不同的容器去建图和表示每个节点的入度信息,下面是拓扑排序问题的步骤:

Step1:建图

建立一个有向图来表示做事情的先后顺序

如何建图–灵活使用语言提供的容器

要存储的是:一个节点与其所相连的节点(边),两点构成一条线段
建立映射关系:
–哈希表存储
Map<Point,List< Point >>

表示每一个节点的入度:
我们是根据入度是否为0来决定先后顺序的

一个节点的入度就是有多少个指向该节点的边

使用数组int[] in表示

Step2.进行拓扑排序(队列 + bfs)

1. 将所有入度为0的节点添加进队列
   

2. 循环队列

   • 获取头结点t,将t添加进入最后的结果之中(如果要表示的话)
   • 将与t相连的边删除–等价于将与t相连的点的入度减1
   • 判断与t相连的点的入度是否为0,如果为0,表示是新的起点,添加进队列之中

3. 直到图中没有节点或者没有入度为0的节点(有环)
   

注意有环的情况

一.课程表

题目链接:课程表

分析:

拓扑排序

• 如果最后存在入度不为0的点–证明有环–无法按照p数组的顺序完成课程
• 全为0,证明可以完成所有课程

代码:

class Solution {// 本题节点就是所有的可成public boolean canFinish(int n, int[][] p) {// 1.建图Map<Integer,List<Integer>> edges = new HashMap<>();int[] in = new int[n];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]++;// 入度加1}// 2.拓扑排序Queue<Integer> q = new LinkedList<>();for(int i = 0; i < n; i++)// 将所有入度为0的点添加进入队列if(in[i] == 0)q.add(i);// bfs// 得到对头元素 -- 删除与其相连的边 -- 找到下一个起始位置while(!q.isEmpty()) {int t = q.poll();for(int i : edges.getOrDefault(t,new ArrayList<>())) {// 将与t相连的点的入度减1in[i]--;if(in[i] == 0) q.add(i);// 如果入度为0,表示新的起点,添加进队列}}// 判断是否存在入度不为0 的点,如果存在,证明有环,则无法完成所有课程,返回falsefor(int i : in)if(i != 0) return false;return true;}
}

总结:

1. 注意本题p数组的指向,是b指向a
2. 大致的过程很简单
   • 建图:建立点与点之间的联系(Map),统计所有点的入度情况–循环遍历即可
   • 拓扑排序:先将所有入度为0的点添加进入队列(起点),bfs循环遍历
3. 一定要注意我们建的图可能有环,也可能无环,如果有环,最后图中一定有入度不为0的节点

二.课程表II

题目链接:课程表II

分析:

和上一道题目相同 只需记录排序结果即可

代码:

import java.util.Collections;
class Solution {public int[] findOrder(int n, int[][] p) {// 1.建图Map<Integer,List<Integer>> edges = new HashMap<>();int[] in = new int[n];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]++;// 入度加1}// 2.拓扑排序Queue<Integer> q = new LinkedList<>();for(int i = 0; i < n; i++)// 将所有入度为0的点添加进入队列if(in[i] == 0)q.add(i);int[] ret = new int[n];int index = 0;// bfswhile(!q.isEmpty()) {int t = q.poll();ret[index++] = t;for(int i : edges.getOrDefault(t,new ArrayList<>())) {// 将与t相连的点的入度减1in[i]--;if(in[i] == 0) q.add(i);// 如果入度为0,表示新的起点,添加进队列}}return index == n ? ret : new int[]{};}
}

三.⽕星词典

题目链接:⽕星词典

分析:

这里面的节点就是一个一个字符,题目最终要求的是字符的先后顺序–拓扑排序
三步:建图,拓扑排序,判断

代码:

class Solution {Map<Character,List<Character>> edges = new HashMap<>();// 建图使用Map<Character,Integer> in = new HashMap<>();// 统计每一个节点的入度信息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 n = words.length;for(int i = 0; i < n - 1; i++) {for(int j = i + 1; j < n; j++) {String s1 = words[i], s2 = words[j];int len = Math.min(s1.length(),s2.length()), index = 0;while(index < len && s1.charAt(index) == s2.charAt(index))index++;// 处理不合法的情况  s1 = abc  s2 = abif(index == s2.length() && index < s1.length()) return "";// 走到两个字符串不相同的字母if(index >= len) continue;// 防止越界char prev = s1.charAt(index), behind = s2.charAt(index);if(!edges.containsKey(prev))edges.put(prev,new ArrayList<>());if(!edges.get(prev).contains(behind)) {// 这里不加if判断也行,加了是为了减少冗余信息的加入edges.get(prev).add(behind);in.put(behind,in.get(behind) + 1);}}}// 2.拓扑排序StringBuffer ret = new StringBuffer();Queue<Character> q = new LinkedList<>();for(char ch : in.keySet()) // 将度为0的节点添加进队列之中if(in.get(ch) == 0) q.add(ch);while(!q.isEmpty()) {char t = q.poll();ret.append(t);// 遍历相连的点for(char ch : edges.getOrDefault(t,new ArrayList<>())) {in.put(ch,in.get(ch) - 1);if(in.get(ch) == 0) q.add(ch);}}// 判断是否存在入度不为0的点for(char ch : in.keySet()) if(in.get(ch) != 0) return "";return ret.toString();}
}