拓扑排序Topologic Sort

一．定义

拓扑排序就是在一个有向无环图中，将所有顶点排成一个线性序列，使得在途中任意一对定点U,V，若<u,v>∈E(G)，则U出现在线性序列V之前。通常将这样的线性序列称为满足拓扑次序的序列，简称为拓扑序列。

 

二. 算法

 

a)扫描顶点表，将入度为零的顶点入栈；

b)当栈非空时：

输出栈顶元素v，出栈；

检查v的出边，将每条出边的终端顶点的入度减1，若该顶点入度为0，入栈；

c)当栈空时，若输出的顶点小于顶点数，则说明AOV网有回路，否则拓扑排序完成。

 

 三. 实现

 

public static int topSort() {
		int i,j,k = 0;
		boolean isSure = true;
		int countNonPre = 0;
		initial();
		countInDegree();
		int top = -1;
		for (j = 0, countNonPre = 0; j < n; j++) {
			if (indegree[j] == 0) {
				countNonPre ++;
				indegree[j] = top;
				top = j;
			}
		}
		if (countNonPre == 0)
			return 0; 			// 存在环，矛盾
		if (countNonPre > 1) 	// 多个先驱节点
			isSure = false;
		for(i = 0;i < n; i++) {                               //结点个数
			if(top == -1) {		//存在环
				isSure = true;
				return 0;
			}
			int now = top;			//now top都是入度为0的点的下标，相当于两个指针
			top = indegree[top];
			result[k++] = (char) (now + 'A');
			countNonPre = 0;
			indegree[now] = -1;
			for(j = 0; j < n; j++) {
				if(map[now][j]) {
					indegree[j]--;
					if(indegree[j] == 0) {
						countNonPre ++;
						indegree[j] = top;
						top = j;
					}
				}
			}
			if(countNonPre > 1) {	//有多个先驱节点，还要继续判断有没有环
				isSure = false;
				countNonPre = 0;
			}
		}
		if(!isSure) return 2;	// 多个先驱节点
		return 1;				// 找到！
	}

 

   通常的拓扑算法要用两个数组，一个用来记录每个顶点的入度，当入度为0，则进栈
   。另一个数组用作栈数组，记录入度为0的顶点。其实当入度为0的顶点进栈以后，indegree[i]
   ＝0就不再有用，所以可以用indegree[i]记录栈内下一个入度为0的顶点，top指向栈顶顶点号。

 

四. 应用

     神经网络。

 

参考：http://dev.csdn.net/author/fisher_jiang/ebb96def8ef44f00a88db5fffd4e2e9e.html

 

 

参见poj1094