图－拓扑排序

当每个任务有前后置关系时，需要找到一种满足前后置关系的路线，将任务完成。

如果将每个任务看成一个节点，任务之间的前后置关系表示为有向图时，这种路线顺序叫做为图进行拓扑排序。也叫关键路径分析。

这里的图用邻接矩阵法表示，算法的关键是：

1 找到一个没有后继的顶点

2 在图中删除它，放入结果数组中

3 重复 步骤 1 ，步骤 2 直到图中没有多余的节点。

如果图中出现环装结构，则算法无法进行，因为此时任务之间循环成为前置。

关于邻接矩阵法请参见：Graph 图－邻接表法。

要注意的是：满足前后置关系的路径可能不止一条。这里仅仅得到其中的一条。

关键API：

   int noNext()：返回没有后继的节点的下标。

   remove(int index)：删除指定下标的节点，同时在邻接矩阵中删除相对应的行与列。

   main：提供简单的测试。

代码如下：

class Vertex {	//图中的节点
	private Object value;
	Vertex(Object value) {
		this.value = value;
	}
	Object value() { return value; }
	@Override public String toString() { return "" + value; }
}

class Topology {	//用邻接矩阵法表示的图
	private Vertex[] vertexs;
	private Object[][] adjMat;	//记载是否联通	
	private int length = 0;
	private static Object CONN = new Object();	//标致是否联通

	Topology(int size) {
		vertexs = new Vertex[size];
		adjMat = new Object[size][size];
	}

	void add(Object value) {
		assert length <= vertexs.length;
		vertexs[length++] = new Vertex(value);
	}

	void connect(int from, int to) {
		assert from < length;
		assert to < length;
		adjMat[from][to] = CONN;	//标志联通
	}

	void remove(int index) {	//移除指定的顶点
		remove(vertexs,index);	//在顶点数组中删除指定位置的下标
		for(Object[] bs: adjMat) remove(bs,index);	//邻接矩阵中删除指定的列
		remove(adjMat,index);	//在邻接矩阵中删除指定的行
		length--;
	}

	private void remove(Object[] a, int index) {	//在数组中移除指定的元素，后面的元素补上空位
		for(int i=index; i<length-1; i++) a[i] = a[i+1];
	}

	int noNext() {	//寻找没有后继的节点
		int result = -1;
OUT:
		for(int i=0; i<length; i++) {
			for(int j=0; j<length; j++) {
				if(adjMat[i][j] == CONN)continue OUT;	//如果有后继则从外循环继续寻找
			}
			return i;	//如果没有与任何节点相连，则返回该节点下标
		}
		return -1;	//否则返回-1
	}

	Object[] topo() {
		Object[] result = new Object[length];	//准备结果数组
		int index;
		int pos = length;
		while(length > 0) {
			index = noNext();	//找到第一个没有后继的节点	
			assert index != -1 : "图中存在环";
			result[--pos] = vertexs[index]; //放入结果中
			remove(index);	//从图中把它删除
		}
		return result;
	}

	public static void main(String[] args) {
		Topology g = new Topology(20);
		g.add('a');
		g.add('b');
		g.add('c');
		g.add('d');
		g.add('e');
		g.add('f');
		g.add('g');
		g.add('h');

		g.connect(0,3);
		g.connect(0,4);
		g.connect(1,4);
		g.connect(2,5);
		g.connect(3,6);
		g.connect(4,6);
		g.connect(5,7);
		g.connect(6,7);

		for(Object o: g.topo()) System.out.print(o + " ");
		System.out.println();
	}
}

 

评论

3 楼 lixia0417 2010-07-13  

楼主，这个remove用得巧妙，我一般都写三个remove才搞定的；

2 楼 fuliang 2008-08-26  

这个算法效率太低了。

1 楼 run_xiao 2008-08-06  

拓扑排序的另一个解法：可以利用深度遍历，递归地在遍历完每个节点的后继节点后，打印出该节点