拓扑排序中的栈存储结构

近期看数据结构，看到拓扑排序中的栈存储数据结构，上面的栈使用数组进行存储，而非Stack定义，使用的非常妙，分享一下。

拓扑排序的主要思想：（1）选择一个入度为0的顶点并输出；（2）从网中删除此顶点及其所有边；（3）重复执行（1）（2）直到不存在入度为0的顶点；比如下面所示的图（采用邻接表表示）：

设置保存每个顶点的入度值的数组d，则d如下所示：

方式一：直接使用d数组作为栈，栈的使用方式如下：

（1）初始化栈，设置链栈指针top为-1；

（2）将入度为0的元素的d[0]进栈，即：的d[0]=top;top=0;此时top指向d[0]元素，表示顶点v0的入度为0，而d[0]的值为-1，表示栈低；

（3）将入度为0的d[1]进栈，即：d[1]=top;top=1;此时top指向d[1]元素，表示顶点v1的入度为0，而d[1]的值为0，表明下一个入度为0的元素为d[0],即对应下一个入度为0的顶点为v0，d[0]的值为-1，所以此栈当前有两个元素d[1]和d[0];

由上面三步步骤初始化数组d为：

删除顶点v1，得到数组d为：

然后依次删除并输出顶点V4，V0，V2，V3，V5（方式一参考《数据结构（c语言描述）》--徐孝凯。。。）

方式二：除了使用数组d外，另外加一个Stack作为栈的存储结构，每次删除一个节点后判断节点的入度是否为零，如果为零则push入Stack中；

Java代码实现如下：

GraphNode节点定义：

package org.fansy.topological.copy;
/**
 * 图的节点定义，含有两个私有变量
 * data：当前节点值；
 * next：下一个节点；
 * @author Administrator
 *
 */
public class GraphNode {
	private int data;
	private GraphNode next;
	public int getData() {
		return data;
	}
	public void setData(int data) {
		this.data = data;
	}
	public GraphNode getNext() {
		return next;
	}
	public void setNext(GraphNode next) {
		this.next = next;
	}	
	public GraphNode(){}
	public GraphNode(int data){
		this.data=data;
	}
	public GraphNode(String data){
		this.data=Integer.parseInt(data);
	}
	public GraphNode(int data,GraphNode next){
		this.data=data;
		this.next=next;
	}
}

图操作：（图创建和图拓扑遍历）

package org.fansy.topological.copy;
import java.util.*;
/**
 * 图操作类
 * 含有创建图方法
 * 
 * @author Administrator
 *
 */
public class GraphOperation {
	/**
	 * 创建一个含有权值的图
	 * @param nodeSize 节点的个数
	 * @return nodes 图存储结构，数组形式
	 */
	public GraphNode[] createGraphTree(int nodeSize){
		GraphNode[] nodesArr=new GraphNode[nodeSize];
		Scanner input=new Scanner(System.in); //  接收键盘输入每个图节点的next域
		for(int i=0;i<nodeSize;i++){
			nodesArr[i]=new GraphNode(i); // 赋值表头节点
			System.out.println("请输入节点 "+i+" 的next 域(逗号分隔)"+
					"比如[next1,next2]或者[null])：");
			String inputStr=input.next();
			if("null".equals(inputStr)){
				continue;
			}
			String[] nodes=inputStr.split(",");
			if(nodes.length<=0){				
				continue;
			}
			GraphNode temp,tempNext;
			tempNext=new GraphNode(nodes[nodes.length-1].split(":")[0]);
			for(int j=nodes.length-2;j>=0;j--){
				temp=new GraphNode(nodes[j].split(":")[0]); 
				temp.setNext(tempNext);
				tempNext=temp;
			}
			nodesArr[i].setNext(tempNext);
		}
		input.close();
		return nodesArr;
	}
	/**
	 * 拓扑排序算法,使用一个top表示栈
	 * @param gl表头数组
	 * @param nodeSize 节点数目 
	 */
	public void topSort(GraphNode[] gl,int nodeSize){
		long start=System.currentTimeMillis();
		int i,j,k,top;
		GraphNode temp;
		// 定义存储图中每个节点入度的一维整型数组
		int[] d=new int[nodeSize];
		for(i=0;i<nodeSize;i++){
			temp=gl[i].getNext();
			while(temp!=null){
				j=temp.getData();
				d[j]++;
				temp=temp.getNext();  //
			}
		}
		//初始化用于链接入度为0的元素的栈的栈顶指针top为-1
		top=-1;
		// 初始化建立栈
		for(i=0;i<nodeSize;i++){
			if(d[i]==0){
				d[i]=top;
				top=i;
			}
		}
		//每循环一次删除一个顶点及其所有出边
		while(top!=-1){
			j=top;  // j的值为一个入度为零的序号
			top=d[top];//删除栈顶元素
			System.out.print(j+",");//输出一个栈顶元素
			temp=gl[j].getNext(); // temp指向顶点gl[j]的下一个节点
			while(temp!=null){
				k=temp.getData();
				d[k]--;
				if(d[k]==0){// 把入度为零的元素进栈
					d[k]=top;
					top=k;
				}
				temp=temp.getNext();
			}
		}
		System.out.println("array time spend:"+(System.currentTimeMillis()-start));
	}	
	/**
	 * 拓扑排序算法,使用一个Stack表示栈
	 * @param gl表头数组
	 * @param nodeSize 节点数目 
	 */
	public void topSort2(GraphNode[] gl,int nodeSize){
		long start=System.currentTimeMillis();
		int i,j,k;
		Stack<Integer> stack=new Stack<Integer>();
		GraphNode temp;
		// 定义存储图中每个节点入度的一维整型数组
		int[] d=new int[nodeSize];
		for(i=0;i<nodeSize;i++){
			temp=gl[i].getNext();
			while(temp!=null){
				j=temp.getData();
				d[j]++;
				temp=temp.getNext();  // 向下转型
			}
		}
		// 初始化建立栈
		for(i=0;i<nodeSize;i++){
			if(d[i]==0){
				stack.push(i);//  把节点压入栈顶
			}
		}
		//每循环一次删除一个顶点及其所有出边
		while(!stack.isEmpty()&&stack.peek()!=null){
			System.out.print(stack.peek()+",");//输出一个栈顶元素
			temp=gl[stack.pop()].getNext(); // ,删除一个栈顶元素
			while(temp!=null){
				k=temp.getData();
				d[k]--;
				if(d[k]==0){// 把入度为零的元素进栈
					stack.push(k);
				}
				temp=temp.getNext();
			}
		}
		System.out.println("stack time spend:"+(System.currentTimeMillis()-start));
	}	
}

测试程序：

package org.fansy.topological.copy;
import java.util.*;
public class TestTopSort {
	/**
	 * 拓扑排序测试程序
	 * @param args
	 */
	public static void main(String[] args) {
		GraphOperation g=new GraphOperation();
		Scanner scan=new Scanner(System.in);
		System.out.println("输入节点的个数：");
		int nodeSize=scan.nextInt();		
		GraphNode[] nodesArr=new GraphNode[nodeSize];
		nodesArr=g.createGraphTree(nodeSize);
		g.topSort(nodesArr, nodeSize);
		System.out.println("\nstack.......");
		g.topSort2(nodesArr, nodeSize);
		scan.close();
	}
}

输出结果如下：

由上面的结果可以看出，不仅方式一的结构存储非常妙，而且遍历耗时减小。

分享，快乐，成长

转载请注明出处：http://blog.csdn.net/fansy1990