广度优先遍历是按层次遍历，和树的广度优先遍历很像。给定一个顶点，一层一层的往外遍历。可以想象成一组人在向各个方向走迷宫，当遇到路口时等待其他人走到这一层路口，然后分裂成更多的人走这个迷宫。 广度优先遍历是通过队列实现的。 与深度优先不同，paths找到的路径是顶点到目标点最短的路径
/** * 广度优先遍历 * @author yuli * */ public class BreadthFirstSearch implements Paths{ //标记是否被访问列表 private boolean[] marked; //访问的次数 private int count; private int[] edgeTo;源顶点，用来记录寻找路径 private int start;//开始的顶点 public BreadthFirstSearch(UndirectedGraph graph,int start) { //通过顶点数创建访问列表 marked = new boolean[graph.vertexNum()]; this.start = start; edgeTo = new int[graph.vertexNum()]; bfs(graph, start); } //广度优先搜索方法 public void bfs(UndirectedGraph graph,int vertex){ Queue<Integer> queue = new LinkedList<>(); queue.offer(vertex); marked[vertex] = true; //如果队列不为空就循环 while(!queue.isEmpty()){ //获得队头 vertex = queue.poll(); //访问队头 System.out.println(vertex); //遍历邻接点 Iterable<Integer> adj = graph.adj(vertex); for (Integer integer : adj) { //如果邻接点没有被访问就入队 if(!marked[integer]){ //标记邻接点已经被访问了 marked[integer] = true; //记录邻接点的源路径 edgeTo[integer] = vertex; //将邻接点入队 queue.offer(integer); } } } } /** * 是否包含到v的路径 */ @Override public boolean hasPathTo(int v) { //该顶点是否被访问过 return marked[v]; } /** * 找到起始顶点到指定顶点（v）的一条路径 */ @Override public Iterable<Integer> pathTo(int v) { if(!hasPathTo(v)){ return null; } Stack<Integer> path = new Stack<>(); //从路径的顶点，递归回到开始的节点 for(int m = v;m != start ;m = edgeTo[m]){ path.push(m); } path.push(start); return path; } }