做流程图用什么网站,建德营销型网站建设,如何为网站建设内容,wordpress 修改语言包前言#xff1a;
首先我们需要知道什么是拓扑排序#xff1f;
在正式讲解拓扑排序这个算法之前#xff0c;我们需要了解一些前置知识#xff08;和离散数学相关#xff09;
1、有向无环图#xff1a;
指的是一个无回路的有向图。
入度#xff1a;有向图中某点作为图…前言
首先我们需要知道什么是拓扑排序
在正式讲解拓扑排序这个算法之前我们需要了解一些前置知识和离散数学相关
1、有向无环图
指的是一个无回路的有向图。
入度有向图中某点作为图中边的终点的次数之和
出度有向图中某点作为图中边的起点的次数之和
2、AOV网顶点活动图
在有向无环图中用顶点来表示一个活动用边来表示活动的先后顺序的图结构。
举个例子 在下面的这张图中1这个点的入度就是02这个点的入度就是2因为有两条有向线段指向2这个点。
3、拓扑排序
简而言之就是找到事情的先后顺拓扑排序的结果可能不是唯一的。
如何排序
找出图中入度为0的点然后输出删除与该点连接的边重复1、2操作直到图中没有点或者没有入度为0点为止。有可能有环
重要应用判断有向图中是否有环
4、如何用代码实现拓扑排序呢重点
首先我们需要根据题意去建图利用哈希表等容器会结合题目详细解析。
接着建好图后借助队列来一次BFS即可。
1、初始化把所有入度为0的点加入到队列中
2、当队列不为空时
拿出队头元素加入到最终结果中删除与该元素相连的边判断与删除边相连的点是否入度变成0如果入度为0加入到队列中
经典例题1207. 课程表 - 力扣LeetCode
题目描述 题目解析
我们可以根据题意将课程之间的联系抽象成图 而题目所说的判断能否完成所有的课程学习问的就是这个图有无环
知道本题利用拓扑排序解决那第一步就是如何建图呢
灵活使用语言提供的容器。
邻接表
我们可以利用哈希表来实现图中点与点之间的关系。 同时我们也需要另一个容器存储每个点的入度。
原码
class Solution {
public:bool canFinish(int numCourses, vectorvectorint prerequisites) {unordered_mapint,vectorint hash; //邻接表存图vectorint in(numCourses); //标记每个点的入度//开始建图for(auto e : prerequisites){int a e[0];int b e[1];hash[b].push_back(a);in[a];}queueint q;//将度为0的边存到队列中for(int i 0; i numCourses; i)//{cout i endl;if(in[i] 0) q.push(i);}//进行拓扑排序bfswhile(q.size()){int t q.front();q.pop();//将这个点删除并且删除跟他相连的边for(int i : hash[t]){in[i]--;if(in[i] 0) q.push(i);}}//判断是否有环for(auto i : in){if(i 0) return false;}return true;}
};
例题二LCR 114. 火星词典 - 力扣LeetCode
题目描述 题目解析 本题也是拓扑排序的经典例题。
1、如何搜集信息
两层for循环
2、拓扑排序
1、建图
hashchar, hashchar edges;
注意第一个hash表示map类型第二个hash表示set。
这就需要我们对容器的灵活使用
2、统计入度信息
hashchar, int in; 注意必须要初始化
3、如何收集信息双指针
4、细节问题
abc和ab若abc在前明显不符合要求需要提前返回空字符串。
原码
class Solution {
public:string alienOrder(vectorstring words) {unordered_mapchar, unordered_setchar edges; // 邻接表来存储图unordered_mapchar, int in; // 统计入度string ans;int n words.size();//必须要对入度进行初始化不然入度为0的点根本没有存进去for(auto i : words){for(auto k : i)in[k] 0;}for(int i 0; i n; i){for(int j i 1; j n; j){string a words[i];string b words[j];int len1 a.size(), len2 b.size();int len min(len1, len2);int flag 0;for(int k 0; k len; k){//正常情况if(a[k] ! b[k]){if(!edges.count(a[k]) || !edges[a[k]].count(b[k])){edges[a[k]].insert(b[k]);in[b[k]];}flag 1;break;}}//判断特殊情况if(len1 len2 !flag){return ans;}}}//开始拓扑排序queuechar q;//注意map的范围for表示for(auto [a, b]: in){if(b 0){q.push(a);}}while(q.size()){char tmp q.front();q.pop();ans tmp;cout ans endl;for(char i : edges[tmp]){in[i]--;if(in[i] 0) q.push(i);}}//判断是否有环for(auto [a,b] : in){if(b ! 0) return ;}return ans;}
};
