算法起步之拓扑排序

发布时间:2016-12-10 1:29:40 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"算法起步之拓扑排序",主要涉及到算法起步之拓扑排序方面的内容,对于算法起步之拓扑排序感兴趣的同学可以参考一下。

        拓扑排序是图中所有节点的一种线性次序,首先拓扑排序是对有向无环图来说的,如果不满足这个条件则无法拓扑排序,拓扑排序就是遵循一定的规则对节点的排序,规则就是假设在图中有一条边是从a节点出发指向b节点,则在拓扑排序中b节点不可能排在a的前面。其实就是一直寻找入度为0的节点。我们也可以理解成b的完成必须依赖a的完成,a没有完成则b无法进行,其实这样理解的话我们先前说的线性规划也是一种拓扑排序,像我们平时的起床过程也是一种拓扑排序。          拓扑排序的实现: public class TopoSort { public void topsort(int[][]map){ int[] into=new int[map.length]; for (int i = 0; i < map.length; i++) { for (int j = 0; j < map.length; j++) { if (map[i][j]==1) { into[j]++; } } } for (int i = 0; i < into.length; i++) { int j=0; while (into[j]!=0) { j++; if (j>into.length) { return; } } System.out.println(j); into[j]=-1; for (int k = 0; k < into.length; k++) { if (map[j][k]==1) { into[k]--; } } } } 友情提示:转载请注明出处:【作者:idlear  博客:http://blog.csdn.net/idlear】

上一篇:OpenCV+iOS开发使用文档
下一篇:Leetcode Word Ladder II 解题报告

相关文章

相关评论