Dowemo
0 0 0 0

The depth of the graph is starting from the initial vertex, finding whether there's an adjacency point, and if there's no access to access the adjacency point, if.
Deep priority traversal can be thought of as a walking maze, passing through each vertex until there's no way, then back to the last vertex. Therefore, it's a recursive idea. It can be implemented in two ways: method recursion and stack.

Interface paths are classes that abstract the path.

publicclassDepthFirstSearchimplementsPaths{//标记是否被访问列表privateboolean[] marked;
 //访问的次数privateint count;
 privateint[] edgeTo;//源顶点,用来记录寻找路径privateint start;
 /**
 * 
 * @param graph 图对象
 * @param start 开始的节点
 */publicDepthFirstSearch(UndirectedGraph graph,int start){
 //通过顶点数创建访问列表 marked = newboolean[graph.vertexNum()];
 this.start = start;
 edgeTo = newint[graph.vertexNum()];
 dfsForStack(graph, start);
 }
 /**
 * 深度遍历图方法,递归
 * @param graph 图对象
 * @param vertex 顶点下标
 */privatevoiddfs(UndirectedGraph graph,int vertex){
 //将顶点标记为已经被访问 marked[vertex] = true;
 //访问顶点 System.out.println(vertex);
 count++;
 //获取顶点邻接的顶点 Iterable<Integer> adj = graph.adj(vertex);
 //访问邻接的顶点for (Integer integer : adj) {
 //如果顶点没有被访问过,就递归的访问if(!marked[integer]){
 //记录顶点被访问的源路径,因为每个顶点的源被访问一次,所以只会有一个源路径 edgeTo[integer] = vertex;
 dfs(graph,integer);
 }
 }
 }
 /**
 * 非递归,栈实现
 * @param graph
 * @param vertex
 */privatevoiddfsForStack(UndirectedGraph graph,int vertex){
 Stack<Integer> stack = new Stack<>();
 stack.push(vertex);
 while(!stack.isEmpty()){
 vertex = stack.peek();
 //如果没被访问过,就访问if(!marked[vertex]){
 marked[vertex] = true;
 System.out.println(vertex);
 //然后再继续访邻接顶点 Iterable<Integer> adj = graph.adj(vertex);
 for (Integer integer : adj) {
 //访问没有被访问的邻接顶点if(!marked[integer]){
 //将邻接顶点入栈,如果栈中存在,就置顶if(stack.contains(integer)){
 //移除然后在添加就置顶了 stack.removeElement(integer);
 }
 //记录顶点的源顶点 edgeTo[integer] = vertex;
 stack.push(integer);
 }
 }
 }else{
 //访问过就弹出 stack.pop();
 }
 }
 }
 /**
 * 是否包含到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;
 }
}

Path interface

/**
 * 路径接口
 * @author yuli
 *
 */publicinterfacePaths {/**
 * 是否包含到v的路径
 * @param v
 * @return */boolean hasPathTo(int v);
 /**
 * 返回到v经过的路径
 * @param v
 * @return */ Iterable<Integer> pathTo(int v);
}



Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs