文章目录
- 拓扑排序
- 有向无环图(DAG图)
- AOV网(顶点活动图)
- 拓扑排序
- 实现拓扑排序
- 207. 课程表
- 题目解析
- 算法原理
- 代码实现
- LCR 113. 课程表 II
- LCR 114. 火星词典
- 题目链接
- 算法原理
- 代码实现
拓扑排序
有向无环图(DAG图)
先从名字下手:
- 有向——有方向
- 无环——没有带环
入度: 有多少条边指向它
出度: 有多少条边从这个顶点出去
AOV网(顶点活动图)
aov
是有向无环图的一个应用
在有向无环图的基础上,用顶点来表示一个活动,用边表示活动的先后顺序的图结构
拓扑排序
大白话,在aov
网中,找到做事情的先后顺序,这个结果可能不是唯一的
做菜:
- 可以先准备厨具,也可以先买菜
- 如果先买菜,下一步既可以准备厨具,也可以洗菜
- …
如何排序:
每次选择的点,其实都是入度为0的点,拿出来之后,把连接的边进行删除。以此循环,直到图中没有点或者没有入度为0的点为止。
有可能有向图是有环的,找不到入度为零的点了
这也是拓扑排序的一个重要应用:判定有向图图中是否有环
实现拓扑排序
借助队列,进行一次BFS即可
-
初始化,将入度为0的点,加入队列
-
队列不为空的时候:
-
拿出队头元素,加入到最终结果;
-
删除与该元素相连的边
-
判断与删除边相连的点,是否入度变为0
如果入度为0,加入队列
-
207. 课程表
题目链接:207. 课程表
题目解析
要修numCourses
门课程,从0开始标记,到numCourses - 1
。
课程学习是有顺序的,prerequistes[i] = [a, b]
,要学a课程,先得把b课程学了。
要我们判断,能不能学习完所以课程(能否拓扑排序-图中是否有环)。
算法原理
如何建图:
邻接表: 一般用于稀疏图建图
vector<vecotr<int>> edges
只能由于数字unordered_map<int, vector<int>> edges
数字、字符串都可以
根据算法流程,灵活建图:
这里需要指定每个节点的入度是多少,采用vector<int> in
代码实现
class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites){//建图准备unordered_map<int, vector<int>> edges; //邻接表vector<int> in(numCourses); //每个节点的入度//建图for(const auto& e : prerequisites){// b -> aint a = e[0];int b = e[1];//存进邻接表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);}}// bfswhile(q.size()){int t = q.front();q.pop();//修改连接点的入度for(const int& 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;}
};
LCR 113. 课程表 II
题目链接:LCR 113. 课程表 II
这题和上一题一样,只不过是返回的学习顺序,没学完就返回空数组
class Solution {
public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites){vector<int> ret;vector<vector<int>> edges(numCourses);vector<int> in(numCourses);//邻接表建图for(const auto& e : prerequisites){int a = e[0];int b = e[1];edges[b].push_back(a);in[a]++;}//拓扑排序queue<int> q;for(int i = 0; i < numCourses; i++){if(in[i] == 0){q.push(i);}}while(q.size()){int t = q.front();q.pop();ret.push_back(t);for(auto a : edges[t]){in[a]--;if(in[a] == 0){q.push(a);}}}if(ret.size() == numCourses) return ret;else return {};}
};
LCR 114. 火星词典
题目链接:LCR 114. 火星词典
题目链接
有个外星的语言,它们的字典序和我们不一样。
现在给我们它们的词典(已经按照字母顺序排序了),让我们根据这个词典,得到它们的字典序。
算法原理
-
如何搜集信息
两层for循环
-
搜集哪些信息
采用双指针,一前一后遍历就能知道谁在前,谁在后 -
统计信息
到这里,得到了有个有向图,然后拓扑排序,看是否有环
代码实现
- 这是是字符串,建图采用
unordered_map<char, unordered_set<char>> edges
- 统计入度信息,采用哈希表,然后初始化
- 特殊情况
abc
、ab
,如果遍历到一个字符结尾,另一个还没完,就表明前面都是一样的,返回""
class Solution {
public:unordered_map<char, unordered_set<char>> edges; //邻接表存图unordered_map<char, int> in; //入度统计bool check = false; //处理边界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]){// a -> bchar a = s1[i];char b = s2[i];if(!edges.count(a) || !edges[a].count(b)){edges[a].insert(b);in[b]++;}break;}}if(i == s2.size() && i < s1.size()) check = true; }string alienOrder(vector<string>& words){//初始化哈希表for(const auto& s : words){for(const 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(check) 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]){in[ch]--;if(in[ch] == 0) q.push(ch);}}for(auto& [a, b] : in)if(b != 0) return "";return ret;}
};