Dowemo
0 0 0 0

traversal is very similar to the traversal of the tree and the tree. Given a vertex, a layer of traversal. You can imagine that a group of people walk through the maze and wait for others to go to the junction when they come to the junction, and then split into more people.
traversal is achieved by the queue.
Unlike depth, paths found by paths are the shortest path to the point to the target point.

/**
 * 广度优先遍历
 * @author yuli
 *
 */publicclassBreadthFirstSearchimplementsPaths{//标记是否被访问列表privateboolean[] marked;
 //访问的次数privateint count;
 privateint[] edgeTo;////源顶点,用来记录寻找路径privateint start;//开始的顶点publicBreadthFirstSearch(UndirectedGraph graph,int start) {
 //通过顶点数创建访问列表 marked = newboolean[graph.vertexNum()];
 this.start = start;
 edgeTo = newint[graph.vertexNum()];
 bfs(graph, start);
 }
 //广度优先搜索方法publicvoidbfs(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的路径
 */@OverridepublicbooleanhasPathTo(int v) {
 //该顶点是否被访问过return marked[v];
 }
 /**
 * 找到起始顶点到指定顶点(v)的一条路径
 */@Overridepublic Iterable<Integer> pathTo(int v) {
 if(!hasPathTo(v)){
 returnnull;
 }
 Stack<Integer> path = new Stack<>();
 //从路径的顶点,递归回到开始的节点for(int m = v;m!= start ;m = edgeTo[m]){
 path.push(m);
 }
 path.push(start);
 return path;
 }
}



Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs