算法起步之拓扑排序

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

算法起步之拓扑排序

原文：http://www.cnblogs.com/lonelyxmas/p/3562000.html