【刷题24】BFS解决拓扑排序
拓扑排序简介
1.有向无环图
有方向，没有环的图结构
入度与出度
针对一个顶点来说的
入度：有多少的箭头指向该顶点
出度：该顶点有多少箭头指向其他顶点
2.AOV网
也叫活动顶点图，每个顶点表示一个活动，每一条边表示活动的先后顺序
3.拓扑排序
找到做事情的先后顺序，排序结果不唯一
如何排序：
- 找到入度为0的顶点，拿出来
- 删除与该点连接的边
- 重复以上操作，直到图中没有顶点或者没有入度为0的顶点为止（有可能有环——可以判断是否有环->是否可以拓扑排序）
4.实现拓扑排序
- 用一个队列，BFS
- 建图
- 把入度为0的顶点入队列
- 当队列不为空：
- 1、拿出队头元素，加入结果中
- 2、删除与该元素相连的边
- 3、判断：与删除边相连的顶点，入度是否为0，为0加入队列
一、课程表
题目：
思路看注释
代码：
class Solution {
public:
bool canFinish(int n, vector<vector<int>>& prerequisites) {
unordered_map<int, vector<int>> edges;// 邻接矩阵
vector<int> in(n);// 入度
// 建图
for(auto& e : prerequisites)
{
int a = e[0];
int b = e[1];
edges[b].push_back(a);// b->a
in[a]++;
}
// 拓扑排序
queue<int> q;
// 所有入度为0的点入队列
for(int i=0; i<n; i++)
{
if(in[i] == 0)
{
q.push(i);
}
}
// 取出队头，排序，判断-入度
while(!q.empty())
{
int t = q.front();
q.pop();
for(auto& e : edges[t])
{
in[e]--;
if(in[e] == 0)
{
q.push(e);
}
}
}
// 判断-有环
for(int i=0; i<n; i++)
{
if(in[i]) return false;
}
return true;
}
};
二、课程表ll
题目：
代码：
class Solution {
public:
vector<int> findOrder(int n, vector<vector<int>>& prerequisites) {
unordered_map<int, vector<int>> edges;// 邻接矩阵
vector<int> in(n);// 入度
vector<int> ret;// 返回值
// 建图
for(auto& e : prerequisites)
{
int a = e[0];
int b = e[1];
edges[b].push_back(a);// b->a
in[a]++;
}
// 拓扑排序
queue<int> q;
// 入度为0的点进队列
for(int i=0; i<n; i++)
{
if(in[i] == 0)
{
q.push(i);
}
}
// 取出队头，排序，判断-入度为0进队列
while(!q.empty())
{
int t = q.front();
q.pop();
ret.push_back(t);//
for(auto &e : edges[t])
{
in[e]--;
if(in[e] == 0)
{
q.push(e);
}
}
}
// 返回 - 先要判断下是否有环
for(int i=0; i<n; i++)
{
if(in[i]) return {};
}
return ret;
}
};
三、火星词典
题目：
代码：
class Solution {
public:
unordered_map<char, unordered_set<char>> edges;// 邻接表
unordered_map<char, int> in;// 统计入度
bool check = false;// 检查是否合法
string alienOrder(vector<string>& words) {
int n = words.size();
// 初始化入度为0
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(check) return "";
}
}
// 拓扑排序
queue<char> q;
for(auto &[a, b] : in)
{
if(b == 0) q.push(a);
}
// 实现拓扑排序
string ret; // 返回值
while(!q.empty())
{
char t = q.front();
q.pop();
ret += t; // 加入结果中
for(auto& 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];
char b = s2[i];
// 没有存过a 或者 存过a，a连接b没有重复
if(!edges.count(a) || !edges[a].count(b))
{
edges[a].insert(b);// a->b
in[b]++;// 入度++
}
break;// 有不同直接跳，后面不用再重复判断了
}
}
// abc ab 返回 ""
if(i == s2.size() && i < s1.size())
{
check = true;
}
}
};
原文地址：https://blog.csdn.net/2301_77459845/article/details/144650524
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！