原文:
算法起步之拓扑排序
拓扑排序是图中所有节点的一种线性次序,首先拓扑排序是对有向无环图来说的,如果不满足这个条件则无法拓扑排序,拓扑排序就是遵循一定的规则对节点的排序,规则就是假设在图中有一条边是从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】