目录
拓扑排序
1.如何排序？
2.如何形成拓扑排序
3.如何建图
1.看数据稠密度
2. 根据算法流程灵活建图
1.课程表
2.课程表2
3.火星词典
拓扑排序
找到做事情的先后顺序，拓扑排序的结果可能不是唯一的
1.如何排序？
1.找出图中入度为0的点，然后输出
2.删除与该点连接的边
3.重复1.2操作，直到图中没有点 或者 图中没有度为0的点为止（因为有可能有环）
2.如何形成拓扑排序
借助队列，来一次bfs即可
1.初始化：把所有入度为0的点加入队列中即可
2.当队列不为空的时候：
a.拿出队头元素，加入到最终结果中
b.删除与该元素相连的边
c.判断 与删除边相连的点，是否入度变成0
如果入度为0，加入到队列中
3.如何建图
我们应该灵活使用stl里面的容器
1.看数据稠密度
我们可以用邻接矩阵和邻接表
邻接表我们可以使用vector嵌套vector，也可以使用哈希表，其中哈希表比较通用一些。
2. 根据算法流程灵活建图
比如要统计每个节点的入度 我们用一个vector<int> 来统计
1.课程表
207. 课程表 - 力扣（LeetCode）
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
//1.准备工作
unordered_map<int, vector<int>> edges;//邻接表存图
vector<int> in(numCourses); // 标记每一个定义的入度
//2.建图
for(auto& e: prerequisites)
{
int a = e[0];
int b = e[1];
edges[b].push_back(a);
in[a]++;
}
//3.拓扑排序
queue<int> q;
//a.把所有入度为0的点加入到队列中
for(int i = 0; i < numCourses; i++)
{
if(in[i] == 0)q.push(i);
}
//b.bfs
while(q.size())
{
int t = q.front();
q.pop();
for(int a: edges[t])
{
in[a]--;
if(in[a] == 0)q.push(a);
}
}
//4.判断是否有环
for(int i = 0; i < numCourses; i++)
{
if(in[i])return false;
}
return true;
}
};2.课程表2
LCR 113. 课程表 II - 力扣（LeetCode）
只需要在pop的时候把相应元素加入数组中即可
class Solution {
public:
vector<int> findOrder(int n, vector<vector<int>>& prerequisites) {
unordered_map<int, vector<int>> hash;
vector<int> in(n,0);
vector<int> ret;
vector<int> ret2;
for(auto e:prerequisites)
{
int a = e[0];
int b = e[1];//b->a
hash[b].push_back(a);
in[a]++;
}
queue<int> q;
for(int i = 0; i < n; i++)
{
if(in[i] == 0)q.push(i);
}
while(q.size())
{
int t = q.front();
ret.push_back(t);
q.pop();
for(auto e: hash[t])
{
in[e]--;
if(in[e] == 0)q.push(e);
}
}
for(auto e: in)
{
if(e)return ret2;
}
return ret;
}
};3.火星词典
LCR 114. 火星词典 - 力扣（LeetCode）
如何搜集信息？两层for循环
拓扑排序
1.建图
我们采用两层哈希嵌套hash<char, hash<char>> edges.
2.统计入度信息
hash<char, int> in
必须要初始化， 不然刚开始的时候找不到入度为0的值。（遍历一下每个字符串即可）
3.如何收集信息
双指针
4.细节问题
一些特殊子串一定是排在对应字符串前面的
出现下面这种情况 我们直接返回空
class Solution {
unordered_map<char, unordered_set<char>> edges;//邻接表存储图
unordered_map<char, int> in; //统计入度
bool cheak; // 处理边界情况
public:
string alienOrder(vector<string>& words) {
//1.初始化哈希表 + 建图
for(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(words[i], words[j]);
if(cheak)return "";
}
}
//2.拓扑排序
queue<char> q;
for(auto& [a, b] : in)
{
if(b == 0)q.push(a);
}
string ret;
while(q.size())
{
char t = q.front();
q.pop();
ret += t;
for(char ch: edges[t])
{
if(--in[ch] == 0)q.push(ch);
}
}
//3.判断
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];
char b = s2[i];// a->b
if(!edges.count(a) || !edges[a].count(b))
{
edges[a].insert(b);
in[b]++;
}
break;
}
}
if(i == s2.size() && i < s1.size())cheak = true;
}
};
