广度优先搜索与深度优先搜索

广度优先搜索的方式模仿二叉树的层序遍历，利用一个队列存储adjacency vertex,利用white,gray and black 标示节点的三种状态。white表示未访问，gray表示已发现但为访问，也就是处于队列节点的状态，black表示已访问，也就是从队列中d出的节点。

/*图算法*/
	//breath first search
	public static<T> LinkedList<T> bfs(DiGraph<T> g,T sVertex)
	{
		//queue stores adjaceent vertices; list stores visited vertices
		LinkedQueue<T> visitQueue=new LinkedQueue();
		LinkedList<T> visitList=new LinkedList<T>();
		Set<T> edgeSet;
		Iterator<T> edgeIter;
		T currVertex=null,neighborVertex=null;
		//check that starting vertex is valid
		if(!g.containsVertex(sVertex))
		{
			throw new IllegalArgumentException("bfs():starting vertex not in the graph");
		}
		//color all vertices WHITE
		g.colorWhite();
		
		//initialize queue with starting vertex
		visitQueue.push(sVertex);
		while(!visitQueue.isEmpty())
		{
			
			//remove a vertex from the queue,color it blace and add to the list of visited vertices
			currVertex=visitQueue.pop();
			g.setColor(currVertex, VertexColor.BLACK);
			//obtain the set of neighbors for current vertex
			visitList.add(currVertex);
			edgeSet=g.getNeighbors(currVertex);
			//sequence through the neighbors and look for vertices
			//that have not been visited
			edgeIter=edgeSet.iterator();
			while(edgeIter.hasNext())
			{
				neighborVertex=edgeIter.next();
				if(g.getColor(neighborVertex)==VertexColor.WHITE)
				{
					//color unvisited vertex Gray and push it onto queue
					g.setColor(neighborVertex, VertexColor.GRAY);
					visitQueue.push(neighborVertex);
				}
			}
			
		}
		return visitList;
	}
	/*图算法*/

广度优先访问的是当前节点可达的所有节点

深度优先，模仿二叉树的后序遍历，只有在访问所有或许节点后方可访问。深度优先是一种可以区分节点发现时间和结束时间的算法，并且可以利用深度优先发现图中环的存在。深度优先返回的列表是按照每个节点结束时间相反的顺序。

	public static<T> void dfsVisit(DiGraph<T> g,T sVertex,LinkedList<T>dfsList,boolean checkForCycle)
	{
		T neighborVertex;
		Set<T> edgeSet;
		//iterator to scan the adjacency set of a vertex
		Iterator<T> edgeIter;
		VertexColor color;
		if(!g.containsVertex(sVertex))
		throw  new IllegalArgumentException("dfs():vertex not in the graph");
		//color vertex gray note its discovery
		g.setColor(sVertex,VertexColor.GRAY);
		edgeSet=g.getNeighbors(sVertex);
		//sequence through the adjacency set and look for vertices that are not yet discovered
		//recursively call dfsVisit() for each such vertex if a vertex in the adjacency list is GRAY, the vertex was discovered during a previous call and there
		//is a cycle that begins and ends at the vertex;if checkForCycle is true ,throw an Exception
		edgeIter=edgeSet.iterator();
		while(edgeIter.hasNext())
		{
			neighborVertex=edgeIter.next();
			color=g.getColor(neighborVertex);
			if(color==VertexColor.WHITE)
				dfsVisit(g,neighborVertex,dfsList,checkForCycle);
			else if(color==VertexColor.GRAY&&checkForCycle)
			{
				throw new IllegalPathStateException("dfsVisit():graph has a cycle!");
			}
		}
		//finished with vertex sVertex; make it BLACK
		//and add it the front of dfsList
		g.setColor(sVertex,VertexColor.BLACK);
		dfsList.addFirst(sVertex);
		  
	}