BFS 解决拓扑排序 , 课程表 , 课程表 II , 火星词典
拓扑排序简介
1.有向无环图(DAG图)
像这样只能从一个点到另一个点有方向的图,并且不构成环状就是有向无环图
如果像这样,4,5,6就构成环状了,就不是有向无环图了。
出度是指一个顶点作为起点出发的边的数量,而入度是指指向该顶点的边的数量
2.AOV网:顶点活动图
在有向无环图中,用顶点来表示一个活动,用边来表示活动的先后顺序的图结构。
eg:
3.拓扑排序
找到做事情的先后顺序,拓扑排序的结果可能不是唯一的。
重要应用:判断有向图中是否有环
用上面那个炒菜的例子:
1.先把买菜拿出来(买菜没有被任何箭头指向,准备厨具也可以)
- 准备厨具和洗菜都可以拿出来
- 只能选择洗菜
5. 可以选择腌肉或者切菜(剩下依次类推)
如何排序
- 找出图中入度为0的点,然后输出
- 删除与该点连接的边
- 重复1,2操作,直到图中没有点或者没有入度为0的点(有可能有环)为止
4.实现拓扑排序
借助队列,来一次bfs即可
- 初始化,把所有入度为0的点加入队列中
- 当队列不为空的时候:
a. 拿出队头元素,加入最终结果中
b. 删除与该元素相连接的边;
c. 判断:与删除边相连接的点,是否入度变为0(如果入度为0,就加入队列)
207. 课程表
由题目可的建网类似这样:
实际上这道题就是在问:
能否拓扑排序
是否是有向无环图 - 有向图中是否有环?
如何建图 ? 灵活的使用容器
更倾向于unordered_map<int, vector> edgs; 建表,就像0 -> 1,2,3 ,好用。
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
unordered_map<int,vector<int>> edges;//邻接表存图
vector<int> in(numCourses); //标记每一个定义的入度
//建图
for(auto& e : prerequisites)
{
int a = e[0], b =e[1]; //b -> a
edges[b].push_back(a);
in[a]++;
}
//拓扑排序
queue<int> q;
//把所有入度为0的点的加入队列
for(int i = 0; i<numCourses; i++)
{
if(in[i] == 0)
q.push(i);
}
//bfs
while(q.size())
{
int t = q.front();
q.pop();
for(auto a : edges[t])
{
in[a]--;
if(in[a] == 0)
q.push(a);
}
}
//判断是否有环
for(int i = 0; i<numCourses; i++)
{
if(in[i])
return false;
}
return true;
}
};
210. 课程表 II
本质上跟上一道题一样,只不过这个让返回课程的学习顺序
我们只需要在每一次取出队列中最上面的时候,把它存入一个vector数组中即可,最后判断数组中的数和课程总数是否相等就可以。
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
unordered_map<int,vector<int>> edgs;//邻接表存图
vector<int> vis(numCourses);//标记每一个定义的入度
//建表
for(auto& e : prerequisites)
{
int a = e[0],b = e[1]; //b->a
edgs[b].push_back(a);
vis[a]++;
}
//拓扑排序
queue<int> q;
vector<int> ret;
//把所有入度为0的点放入队列
for(int i = 0; i<numCourses; i++)
{
if(vis[i] == 0)
q.push(i);
}
while(q.size())
{
int t = q.front();
ret.push_back(t);
q.pop();
for(auto a : edgs[t])
{
vis[a]--;
if(vis[a] == 0)
q.push(a);
}
}
if(ret.size() == numCourses)
return ret;
else return {};
}
};
LCR 114. 火星词典
如何收集信息
用两层for循环来搜集信息
一遍一遍循环比较来建有向无环图
细节问题
像abc 和 ab 这种比较并不合法
class Solution {
public:
unordered_map<char,unordered_set<char>> edges;//邻接表存图
unordered_map<char,int> in; //统计入度
bool valid; //处理边界情况
string alienOrder(vector<string>& words) {
int n = words.size();
//建表+初始化入度哈希表
for(auto& s : words)
{
for(auto ch : s)
{
in[ch] = 0;
}
}
for(int i = 0; i<n; i++)
{
for(int j = i+1; j<n; j++)
{
add(words[i],words[j]);
if(valid) return "";
}
}
//拓扑排序
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);
}
}
//判断
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()) //判断不合法的情况
valid = true;
}
};
原文地址:https://blog.csdn.net/weixin_74461263/article/details/142555005
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!