图的遍历--java实现

最近在看数据结构，之前用c实现，现在用java实现图的算法

public class Graph {
	private final int V;
	private int E;
	private Bag<Integer>[]  adj;
	
	public Graph(int V){
		StdOut.println(V);
		this.V = V;
		this.E = 0;
		adj = (Bag<Integer>[]) new Bag[V];
		for(int v = 0;v < V;v++){
			adj[v]  = new Bag<Integer>();
		}
	}
	public Graph(In in){
		
		this(in.readInt());
		int E = in.readInt();
		for(int i= 0;i < E;i ++){
			int v = in.readInt();
			int w = in.readInt();
			addEdge(v,w);
		}
	}
	int V(){
		return V;
	}
	int E(){
		return E;
	}
	public void addEdge(int v,int w){
		adj[v].add(w);
		adj[w].add(v);
		E++;
	}
	Iterable<Integer> adj(int v){
		return adj[v];
	}
	public String toString(){
		String s = V + " vertices" + E+" edges\n";
		for(int v = 0;v < V;v++){
			s += v + ": ";
			for(int w:this.adj(v))
				s+= w + " ";
		}
		return s;
	}
	
	public static int degree(Graph G,int v){
		int degree = 0;
		for(int w : G.adj(v))
			degree++;
		return degree;
	}
	public static int maxDegree(Graph G){
		int max = 0;
		for(int v = 0; v < G.V();v++){
			if(degree(G,v) > max)
				max = degree(G,v);
		}
		return max;
	}
	
	public static double avgDegree(Graph G){
		return 2.0*G.E()/G.V();
	}
	public static int numberOfSelfLoops(Graph G){
		int count = 0;
		for(int v = 0; v < G.V(); v++){
			for(int w : G.adj(v))
				if(v==w)
					count ++;
		}
		return count/2;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}

再次基础上，实现深度优先搜索遍历

public class BreadthFirstPaths {

	private boolean[] marked;
	private int[] edgeTo;
	private final int s;
	
	public BreadthFirstPaths(Graph G,int s){
		marked = new boolean[G.V()];
		edgeTo = new int[G.V()];
		this.s = s;
		bfs(G,s);
	}
	private void bfs(Graph G,int s){
		Queue<Integer> queue = new Queue<Integer>();
		marked[s] = true;
		queue.enqueue(s);
		while(!queue.isEmpty()){
			int v = queue.dequeue();
			for(int w : G.adj(v)){
				if(!marked[w])
				{
					edgeTo[w] = v;
					marked[w] = true;
					queue.enqueue(w);
				}
			}
			
		}
	}
	
	public boolean hasPathTo(int v){
		return marked[v];
	}
	public Iterable<Integer> pathTo(int v){
		if(!hasPathTo(v))
			return null;
		Stack<Integer> path = new Stack<Integer>();
		for(int x = v; x != s; x = edgeTo[x]){
			path.push(x);
		}
		path.push(s);
		return path;
	}
	public static void main(String[] args) {
		Graph G = new Graph(new In(args[0]));
		int s = Integer.parseInt(args[1]);
		BreadthFirstPaths search = new BreadthFirstPaths(G,s);
		for(int v = 0; v < G.V(); v++){
			StdOut.print(s + " to " + v + ": ");
			if(search.hasPathTo(v)){
				for(int x : search.pathTo(v))
					if(x==s) 
						StdOut.print(x);
					else
						StdOut.print("-" + x);
			}else{
				StdOut.print("null");
			}
			StdOut.println();
		}

	}

}