【基础算法总结】BFS_拓扑排序问题

算法原理：

这道题可以抽象成拓扑排序问题。题目是问能否完成课程学习，其实就是问是否存在拓扑序列，也相当于问这个有向图中是否有环，若有环，则不能完成，否则可以完成。

下一个重点是如何建图?

拓扑建图一般有两种方式，邻接矩阵和邻接表，如何选择就要看数据的稠密程度。数据稀疏就用邻接表，稠密就用邻接矩阵。这里只介绍邻接表。

细节/技巧问题：

(1) 根据拓扑排序的流程，我们还需要知道每个顶点的入度是多少，只有入度为0的才入队列。所以还需要建立一个数组记录入度值。
(2) 在进行最后的判断时，是用点的入度值来判断的。如果存在拓扑序列，则每个点的入度值肯定为0，否则就不存在。

代码实现：
这里我们使用的是unordered_map建立邻接表。

class Solution 
{
public:bool canFinish(int n, vector<vector<int>>& prerequisites) {unordered_map<int, vector<int>> edges; // 邻接表存图vector<int> in(n); // 记录每个顶点的入度// 1.建图for(auto& e : prerequisites){int a = e[0], b = e[1]; // b --> aedges[b].push_back(a); // 一个顶点后面跟着的几个顶点in[a]++; // a的入度+1}// 2.拓扑排序// (1). 把所有入度为0顶点的加入队列中queue<int> q;for(int i = 0; i < n; i++){if(in[i] == 0)q.push(i); // 这里要注意区分，i是指那个顶点，in[i]是该顶点对应的入度值}// (2).bfswhile(q.size()){int t = q.front();q.pop();// 找到这个入度为0顶点所指向的其他顶点，修改它们的入度值// edges[t]是那个数组，用范围for进行遍历，数组里面存的就是那些顶点for(int a : edges[t]){in[a]--;if(in[a] == 0) q.push(a);}}// 3.判断是否有环// 如果不成环，说明已经找出了顺序，入度一定为0，否则就成环了for(int i = 0; i < n; i++)if(in[i]) return false;return true;}
};

算法原理：

这道题和第一题基本一模一样，唯一不同的是如果可以完成课程，本题最后要返回拓扑序列，否则就返回空数组。

细节/技巧问题：

最后检查是否存在拓扑序列时要用那个返回数组的元素个数来判断。如果存在拓扑序列，则元素个数==课程数，否则就不存在。

代码实现：

方式1：哈希表

class Solution 
{
public:vector<int> findOrder(int n, vector<vector<int>>& prerequisites) {unordered_map<int, vector<int>> edges; // 邻接表存图vector<int> in(n); // 记录每个点的入度// 建图for(auto& e : prerequisites){int a = e[0], b = e[1];edges[b].push_back(a);in[a]++;}// 拓扑排序// (1)把入度为0的点入队列queue<int> q;for(int i = 0; i < n; i++){if(in[i] == 0)q.push(i);}vector<int> ret;// (2) bfswhile(q.size()){int t = q.front();q.pop();ret.push_back(t);for(int a : edges[t]){in[a]--; // 把那条边删除if(in[a] == 0) q.push(a);}}// 检查if(ret.size() == n) return ret;else return {};}
};

方式2：二维数组

class Solution 
{
public:vector<int> findOrder(int n, vector<vector<int>>& prerequisites) {vector<vector<int>> edges(n); // 邻接表存图vector<int> in(n); // 记录每个点的入度// 建图for(auto& e : prerequisites){int a = e[0], b = e[1];edges[b].push_back(a);in[a]++;}// 拓扑排序// (1)把入度为0的点入队列queue<int> q;for(int i = 0; i < n; i++){if(in[i] == 0)q.push(i);}vector<int> ret;// (2) bfswhile(q.size()){int t = q.front();q.pop();ret.push_back(t);for(int a : edges[t]){in[a]--; // 把那条边删除if(in[a] == 0) q.push(a);}}// 检查if(ret.size() == n) return ret;else return {};}
};

算法原理：

这道题无论是理解题意还是代码实现都确实很难。首先来理解题意，题目的意思是通过它给出的字符串数组，把每个字符串进行比较，当遇到一个字符不同时，就停止比较，此时前一个字符就比后一个字符的字典序低。

这道题可以抽象为拓扑排序问题。就拿示例1来说： w–>e说明w在e的前面，就是 w<e。

所以题目要求的新的字典序就是拓扑序列。

细节/技巧问题：

(1) 建图。这道题的顶点是字符，所以只能用哈希表建图，但是由于在字符串比较的过程中会出现冗余现象，比如1，3进行比较，得出w–> e，1，4进行比较，也是w–> e。为了避免这种现象可以再嵌套一个哈希。所以最终建图使用的是 hash<char, hasn< char >>。

(2) 统计入度信息。因为这里的字符串不一定有26个字符，所以不方便用 int[26] 的数组统计入度。可以使用哈希表 hash< char, int >记录每个顶点的入度值，但是这里的哈希表必须要初始化。

(3) 还有一种特殊情况就是 abc 和 ab 进行比较的时候，这是不合法的，直接返回空串。

代码实现：

class Solution 
{unordered_map<char, unordered_set<char>> edges; // 邻接表建图unordered_map<char, int> in; // 记录每个顶点对应的入度bool cheak; // 处理特殊情况
public:string alienOrder(vector<string>& words) {// 建图 + 初始化入度哈希表为0for(auto& s : words)for(auto ch : s)in[ch] = 0;int n = words.size();for(int i = 0; i < n; i++){for(int j = i + 1; j < n; j++){// add函数的作用：用边和点建图，判断特殊情况add(words[i], words[j]);if(cheak) return "";}}// 拓扑排序queue<char> q;// (1)把入度为0的入队列for(auto& [a, b] : in)if(b == 0)q.push(a);// (2)bfsstring ret;while(q.size()){char t = q.front();q.pop();ret += t;// 该点指向的点入度-1for(char e : edges[t]){if(--in[e] == 0) q.push(e);}}// 判断是否成环for(auto& [a, b] : in)if(b != 0) return "";return ret;}void add(string& s1, string& s2){int n = min(s1.size(), s2.size());int i = 0;// 遍历比较两个字符串，注意不能越界for(; i < n; i++) {if(s1[i] != s2[i]){char a = s1[i], b = s2[i]; // a --> b// a这点没有检查过或是a检查过，a指向的点没有检查过if(!edges.count(a) || !edges[a].count(b)){edges[a].insert(b);in[b]++;}break; // 第一次发现不同就停止}}// 处理 abc ab 这种特殊情况if(i == s2.size() && i < s1.size()) cheak = true;}
};