图的深度优先遍历的概念与实现

图的深度优先遍历是从初始顶点出发，找到是否有邻接点，判断是否访问过，如果没有访问过访问该邻接点，如果邻接点还有邻接点就继续访问，直到到达没有邻接点可以访问的顶点，就回退到上一个顶点。 深度优先遍历可以想象成走迷宫，一直路过各个顶点，直到没有路了，再回退到上个顶点继续走。因此是递归思想。可以用方法(method)递归和栈（stack）递归两种方式实现。

接口Paths是抽象出遍历路径的类。

public class DepthFirstSearch implements Paths{ //标记是否被访问列表 private boolean[] marked; //访问的次数 private int count; private int[] edgeTo;//源顶点，用来记录寻找路径 private int start; /** * * @param graph 图对象 * @param start 开始的节点 */ public DepthFirstSearch(UndirectedGraph graph,int start){ //通过顶点数创建访问列表 marked = new boolean[graph.vertexNum()]; this.start = start; edgeTo = new int[graph.vertexNum()]; dfsForStack(graph, start); } /** * 深度遍历图方法，递归 * @param graph 图对象 * @param vertex 顶点下标 */ private void dfs(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 */ private void dfsForStack(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的路径 */ @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; } }

paths接口

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