宽度优先扫描和深度优先扫描宽度优先扫描图形代码深度优先扫描图形代码
广度优先遍历
宽度优先扫描是图中的扫描方式之一，如下图所示，考虑扫描与这些点相邻的所有点，并对这些点进行宽度优先扫描
图解首先从a点开始扫描，然后扫描与a相邻的所有点f和点G:
然后，扫描f和点g，得到点e、h、k和B:
然后继续，我知道所有的点都是遍历：完成的。
首先，定义图Graph类：
/** *有向图* /公共类图形/** *顶点数*/private final int V； /** *边数*/private int E； /** *邻接表*/private MapInteger，SetInteger adj； publicgraph(intv ) { this.V=V； this.E=0； for(intI=0； ； I ) ) adj.put(I，new HashSet ) )； } } public int getV () { return this.V； } public int getE () ) { return this.E； } /** *添加边* * @ paramv * @ paramw */publicvoidaddedge (intv，int w ) ) adj.get ) v ).add ) w )； adj.get(w ).add (v )； this.E； }publiciterableintegeradj(intv ) returnthis.adj.get ) v； }然后编写BFS代码。 在此，我们将使用数组marked标记是否访问了点。 这样就不需要再次访问点了。 此外，还可以在队列中保存已遍历的节点，并在每次从队列中取出节点进行访问时将新的已遍历节点添加到队列中。 如果队列中没有节点，则在：结束
上述照片中的队列都是上下排的
/** *广度优先遍历*/publicclassbreadthfirstpaths {/* * *此顶点位于BFS((*/privateboolean[]marked； /**从起点到顶点的已知路径上的最后一个顶点*/private int[] edgeTo； /**起点*/private int s； publicbreadthfirstpaths(graphg，int s ) { this.marked=new boolean [ g.getv ] ]； this.edgeto=newint[g.getv(] () ]； this.s=s； BFS(g，s )； }privatevoidBFS(graphg，int s ) { list integer list=new linked list }； marked[s]=true； list.add(s； while (！ list.isEmpty () (intv=list.get ) ) 0； list.remove(0； for(intw:g.adj ) v ) ) if (！ marked[w]}{edgeto[w]=v； marked[w]=true； list.add(w； }//****s判断s和v是否相连* * @ paramw * @ return */publicbooleanhaspathto (intw ) { return marked[w]； } /** *从起点s到顶点v的路径* * @ paramv * @ return */publiciterableintegerpathto (intv ) if (！ Haspathto(v ) ) { retur
n null; } List<Integer> path = new ArrayList<>(); for (int i = v; i != s; i = edgeTo[i]) { path.add(i); } path.add(s); return path; }} 深度优先遍历深度优先遍历和广度优先不同, 它的思想是每一次值找一个点, 一条路走到底, 然后在返回去遍历第二个点, 这类似于我们走迷宫一直走下去, 知道走到绝路再退回上一个路口走吓一跳道
图解我们同样以点A作为起点, 首先我们选择一条路走到底:
走到绝路了, 退回到点E, 换一条路走:
然后再继续回退, 知道所有的点都遍历完:
我们沿用刚刚定义的Graph类. 我们不难发现, DFS很容易用递归来实现:
** * 深度优先遍历 */public class DepthFirstSearch { /** * 该顶点是否调用了dfs() */ private boolean[] marked; /** * 从起点到一个顶点的已知路径上的最后一个顶点 */ private int[] edgeTo; /** * 起点 */ private int s; /** * 与起点相连接的顶点数 */ private int count; /** * 找出图g中所有和定点s相连的顶点 * * @param g * @param s */ public DepthFirstSearch(Graph g, int s) { this.marked = new boolean[g.getV()]; this.edgeTo = new int[g.getV()]; this.s = s; this.count = 0; dfs(g, s); } private void dfs(Graph g, int v) { marked[v] = true; for (int w : g.adj(v)) { if (!marked[w]) { this.edgeTo[w] = v; dfs(g, w); } } } /** * 判断s和v是否相连接 * * @param w * @return */ public boolean hasPathTo(int w) { return marked[w]; } /** * 返回和s相连接的顶点数目 * * @return */ public int getCount() { return count; } /** * 获取起点s到顶点v的路径 * * @param v * @return */ public Iterable<Integer> pathTo(int v) { if (!hasPathTo(v)) { return null; } List<Integer> path = new ArrayList<>(); for (int i = v; i != s; i = edgeTo[i]) { path.add(i); } path.add(s); return path; }}当然, 我们同样的可以用栈来实现DFS, 将访问的节点入栈, 访问完就出栈, 这样也可以做到DFS:
private void dfsByStack(Graph g, int v) { marked[v] = true; Stack<Integer> stack = new Stack<>(); stack.push(v); while (!stack.empty()) { int u = stack.peek(); int w = u; for (int i : g.adj(v)) { if (!marked[i]) { w = i; break; } } if (w != u) { this.edgeTo[w] = v; stack.push(w); } else { stack.pop(); } } }