digraph.java

使用Java实现的Graph的迭代加深的深度优先搜索

/**
 * 
 */
package digraph;

import java.util.*;

/**
 * @author zhangli
 *
 */
public class DiGraph implements Graph {
	private List<Node> nodesList;
	private Hashtable<String, Node> nodesTable;
	
	private int edgeNumber;
	private int nodeNumber;

	private List<List<Node>> allPathList;
	private List<Node> pathStack;
	private boolean found;


	public DiGraph()
	{
		nodesList = new ArrayList<Node>();
		nodesTable = new Hashtable<String, Node>();
		edgeNumber = 0;
		nodeNumber = 0;
	}
	
	public void addEdge(Node node1, Node node2) {
		// TODO Auto-generated method stub
		node1.addSuccessor(node2);
		node2.addPredecessors(node1);
		edgeNumber++;
	}

	public Node addNode(String nodeName) {
		// TODO Auto-generated method stub
		Node node = new DiNode(nodeName);
		nodesList.add(node);
		nodesTable.put(nodeName, node);
		nodeNumber++;
		return node;
	}

	public int edgeNumber() {
		// TODO Auto-generated method stub
		return edgeNumber;
	}
	
	public int nodeNumber() {
		// TODO Auto-generated method stub
		return nodeNumber;
	}
	
	public Node getNode(String nodeName) {
		// TODO Auto-generated method stub
		return nodesTable.get(nodeName);
	}

	public List getPredecessors(Node node) {
		// TODO Auto-generated method stub
		return node.getPredecessors();
	}

	public List getSuccessors(Node node) {
		// TODO Auto-generated method stub
		return node.getSuccessors();
	}

	@SuppressWarnings("unchecked")
	public boolean hasEdge(Node node1, Node node2) {
		// TODO Auto-generated method stub
		List<Node> list = node1.getSuccessors();
		for (Node sucNode : list)
		{
			if (sucNode == node2)
				return true;
		}
		return false;
	}
	
	private void iterativeDFS(Node dest, Node node, int depth, int maxDepth)
	{
		if (depth >= maxDepth || node.getSuccessors().size() == 0)
			return;

		pathStack.add(node);

		for (int i=0; i<node.getSuccessors().size(); i++)
		{
			Node sucNode = (Node)node.getSuccessors().get(i);
			
			if (sucNode == dest)
			{
				pathStack.add(sucNode);
				List<Node> newPath = new LinkedList<Node>(pathStack);
				allPathList.add(newPath);
				found = true;
				pathStack.remove(pathStack.size()-1);
			}
			
			iterativeDFS(dest, sucNode, depth+1, maxDepth);
		}
		
		pathStack.remove(pathStack.size()-1);
		
	}
	
	public List getShortestPath(Node src,Node dest)
	{
		pathStack = new LinkedList<Node>();
		allPathList = new ArrayList<List<Node>>();
		found = false;
		
		for (int i=3; !found; i++)
		{
			iterativeDFS(dest, src, 1, i);
		}
		
		return allPathList;
	
	}
	
	
}