近期看数据结构，看到拓扑排序中的栈存储数据结构，上面的栈使用数组进行存储，而非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