无向图----广度优先搜索

public class BreadthFirstPaths {
	private boolean[] marked;
	private int[] edgeTo;
	private 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];}
}