LeetCode编程训练 - 拓扑排序(Topological Sort)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode编程训练 - 拓扑排序(Topological Sort)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1955字，纯文字阅读大概需要3分钟。
内容图文
拓扑排序基础
拓扑排序用于解决有向无环图(DAG,Directed Acyclic Graph)按依赖关系排线性序列问题，直白地说解决这样的问题：有一组数据，其中一些数据依赖其他，问能否按依赖关系排序(被依赖的排在前面)，或给出排序结果。
最常用解决拓扑排序问题的方法是Kahn算法，步骤可以概括为：
1. 根据依赖关系，构建邻接矩阵或邻接表、入度数组 2. 取入度为0的数据(即不依赖其他数据的数据)，根据邻接矩阵/邻接表依次减小依赖其的数据的入度 3. 判断减小后是否有新的入度为0的数据，继续进行第2步 4. 直到所有数据入度为0、得到拓扑排序序列，或返回失败(存在环形依赖)
其中2、3两个步骤取入度为0数据、减小依赖其的数据的入度，过程像树的宽度优先搜索，用到类似BFS方法；以上过程用伪代码表示如下：
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge
while S is non-empty do
remove a node n from S
add n to tail of L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
下面看具体例子 207. Course Schedule (有n个课程，课程间有依赖关系，问能否完成所有课程)：
//207. Course Schedule
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
//构建邻接矩阵、入度数组
vector<vector<int>> adj(numCourses);
vector<int> indegree(numCourses,0);
for(auto x:prerequisites){
adj[x.second].push_back(x.first);
indegree[x.first]++;
}
//类似BFS
queue<int> q;
for(int i=0;i<numCourses;i++)
if(indegree[i]==0) q.push(i);
while(!q.empty()){
int cur=q.front();
q.pop();
numCourses--;
for(auto next:adj[cur])
if(--indegree[next]==0) q.push(next);//新入度为0的先处理，这与正统BFS有区别
}
//判断最后所有数据入度为0
return numCourses==0;
}
以上用到邻接矩阵(adjacency matrix)表示依赖关系，时间复杂度为O(V^2)，其中V为数据个数。可视化过程：这里
相关LeetCode题：
444.?Sequence Reconstruction 题解
? ? ?
内容总结
以上是互联网集市为您收集整理的LeetCode编程训练 - 拓扑排序(Topological Sort)全部内容，希望文章能够帮你解决LeetCode编程训练 - 拓扑排序(Topological Sort)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。