有向无环图的拓扑排序

package com.data.struct;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import com.data.struct.GraphicDepthFirst.Node;


public class GraphicDepthFirstSort {
	private Node[] list;
	private int time=0;
	private List<Node> sortList=new ArrayList<Node>();
	public GraphicDepthFirstSort(int v,int e){
		list=new Node[v];
		for(int i=0;i<v;i++){
			Node node=new Node();
			node.id=i;
			list[i]=node;
		}
		for(int i=0;i<e;i++){
			int v1=new Random().nextInt(v);
			int v2=new Random().nextInt(v);
			if(v1==v2){
				continue;
			}
			while(true){
				Node node=list[v1];
				boolean already=false;
				while(node.next!=null){
					if(node.next.id==v2){
						already=true;
						break;
					}
					node=node.next;
				}
				if(already==true){
					break;
				}
				Node ex=new Node();
				ex.id=v2;
				node.next=ex;
				break;
			}
		}
	}

	public List<Node> getSort(){
		return sortList;
	}
	public void printSort(){
		System.out.println("sort===========");
		for(int i=0;i<sortList.size();i++){
			System.out.print(sortList.get(i).id+"  ");;
		}
		System.out.println();
	}

	public void depthFirstSearch(){
		for(int i=0;i<list.length;i++){
			if(list[i].color==Node.WHITE){
				dfsVisit(list[i]);
			}
		}
	}

	private void dfsVisit(Node node){
		time++;
		node.d=time;
		node.color=Node.GRAY;
		Node w=list[node.id];
		Node u=w;
		while(w.next!=null){
			if(list[w.next.id].color==Node.WHITE){
				list[w.next.id].color=Node.GRAY;
				list[w.next.id].parent=u;
				dfsVisit(list[w.next.id]);
			}
			w=w.next;
		}
		node.color=Node.BLACK;
		time++;
		node.f=time;
		sortList.add(0, node);
	}

	public void printDepth(Node v){
		Node s=list[0];
		if(v==s){
			System.out.print(s.id+"=>");
		}else if(v.parent==null){
			System.out.print(v.id+"=>");
		}else {
			printDepth(v.parent);
			System.out.print(v.id+"=>");
		}
	}

	public void print(){
		for(int i=0;i<list.length;i++){
			Node node=list[i];
			System.out.print(node.id+"=>");
			while(node.next!=null){
				System.out.print(node.next.id+"=>");
				node=node.next;
			}
			System.out.println();
		}

	}
	public void printAllDepth(){
		System.out.println("path");
		for(int i=0;i<list.length;i++){
			printDepth(list[i]);
			System.out.println();
		}
	}

	public static class Node{
		public static final int WHITE=1;
		public static final int BLACK=2;
		public static final int GRAY=3;
		private int id;
		private Node next;
		private int color=WHITE;
		private int d=Integer.MAX_VALUE;
		private Node parent;
		private int f;
	}
	public static void main(String[] args)throws Exception {
		GraphicDepthFirstSort g=new GraphicDepthFirstSort(5,30);
		g.print();
		g.depthFirstSearch();
		g.printAllDepth();
		g.printSort();


	}

}

上面构造的图，并不是有向无环图，但结果如果把它当作有向无环图，结果是正确的。