前言
在上一篇中咱们把图通过邻接表数组示意进去了，这个数据结构将会做咱们实现图算法的根底，本篇咱们将一起开始学习图算法的第一个搜索算法 - 深度优先搜寻
搜寻API的定义
public class Search { Search(Graph graph, int s); boolean marked(int v); int count();}在开始实现算法之前，咱们仍然先来定义搜寻的API
- 构造方法提供了一个图对象，以及一个终点s，须要找到与s连通的所有顶点
- marked判断顶点s与v是否相邻
- count返回与顶点s相连的总顶点数
深度优先搜寻
如果上图是一个迷宫，咱们须要从顶点0开始找到一条前途，假如咱们有一条有限长的绳子，和一支粉笔，那么能够这样思考找到前途：
- 先抉择一条通道走，在走的路上放上一根绳子
- 每遇到一个路口就用笔标记一下，持续抉择一条未走过的通道
- 当遇到一个曾经被标记的路口时就退回到上一个路口持续抉择一个未走过的通道
- 当回退的路口曾经没有路能够走的时候就在持续往后回退
这种形式绳子总能帮你找到一条前途，而标记不会让你反复走曾经走过的通道。
深度优先搜寻的实现思路就和走迷宫的形式一样；
public class DepthFirstSearch { private boolean marked[]; private int count; public DepthFirstSearch(Graph graph, int s) { this.marked = new boolean[graph.V()]; this.dfs(graph, s); } private void dfs(Graph graph, int v) { marked[v] = true; count++; for (int w : graph.adj(v)) { if (!marked[w]) { dfs(graph, w); } } } @Override public boolean marked(int v) { return marked[v]; } @Override public int count() { return count; }}在搜寻一张图的时候，应用递归来遍历所有的顶点，在拜访其中一个顶点时：
- 标记它被曾经拜访
- 递归的拜访与之相连的所有邻接点
单元测试：
构建上面这张图，而后测试深度优先搜寻
@Testpublic void test() { Graph graph = new Graph(8); //构建一张图 graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(0, 5); graph.addEdge(1, 3); graph.addEdge(2, 4); graph.addEdge(4, 3); graph.addEdge(5, 3); graph.addEdge(6, 7); //为了展现 SeDepthFirstSearcharch search = new DepthFirstSearch(graph, 0); System.out.println(search.count()); System.out.println(search.marked(6)); System.out.println(search.marked(7)); System.out.println(search.marked(2)); System.out.println(search.marked(5));}寻找门路的API
以上的递归算法只是一个开始，从下面的后果咱们能够看出，咱们只能判断出哪些顶点与终点s是连通的，无奈给出具体的门路进去；换句话说，咱们须要实现从顶点s到顶点v是否存在门路可达，如果存在请打印进去
public class Paths { Paths(Graph graph, int s); boolean hasPathTo(int v); //判断出从s->v是否存在门路 Iterable<Integer> pathTo(int v); //如果存在门路，返回门路}基于深度优先搜寻查找图中的可达门路
咱们仍然基于这张图来看，因为咱们须要找出可达的门路，所以咱们在进行搜寻的时候须要记录下图中的边，这里咱们应用的是一个数组edgeTo[]，如果存在一条边是v->w，那么能够示意成edgeTo[w]=v，在深度搜寻实现之后这个edgeTo[]数组就是一颗由父链示意的一颗树
（父链树在之前的文章中也应用过《如何检测社交网络中两个人是否是敌人关系（union-find算法）》）
public class DepthFirstPaths { private boolean marked[]; private int[] edgeTo; private int s; DepthFirstPaths(Graph graph, int s) { this.s = s; this.marked = new boolean[graph.V()]; this.edgeTo = new int[graph.V()]; this.dfs(graph, s); } private void dfs(Graph graph, int v) { this.marked[v] = true; for (int w : graph.adj(v)) { if (!marked[w]) { this.edgeTo[w] = v; this.dfs(graph, w); } } } public boolean hasPathTo(int v) { return marked[v]; } public Iterable<Integer> pathTo(int v) { if (!hasPathTo(v)) { throw new IllegalStateException("s不能到达v"); } Stack<Integer> stack = new LinkedListStack<>(); stack.push(v); while (edgeTo[v] != s) { stack.push(edgeTo[v]); v = edgeTo[v]; } stack.push(s); return stack; }}画图来具体跟踪深度优先搜寻的运行轨迹，记录了edgeTo的变动以及父链树的逐步造成
最终父链树造成了，接下来咱们来写单元测试校验下生成的父链树和理论的运行后果是否统一
@Testpublic void test() { Graph graph = new Graph(8); graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(0, 5); graph.addEdge(1, 3); graph.addEdge(2, 4); graph.addEdge(4, 3); graph.addEdge(5, 3); graph.addEdge(6, 7); DepthFirstPaths paths = new DepthFirstPaths(graph, 0); System.out.println(paths.hasPathTo(5)); System.out.println(paths.hasPathTo(2)); System.out.println(paths.hasPathTo(6)); paths.pathTo(5).forEach(System.out::print); System.out.println(); paths.pathTo(4).forEach(System.out::print); System.out.println(); paths.pathTo(2).forEach(System.out::print);}验证后果齐全匹配了父链树
文中所有源码已放入到了github仓库:
https://github.com/silently9527/JavaCore
最初（点关注，不迷路）
文中或者会存在或多或少的有余、谬误之处，有倡议或者意见也十分欢送大家在评论交换。
最初，写作不易，请不要白嫖我哟，心愿敌人们能够点赞评论关注三连，因为这些就是我分享的全副能源起源
吐血整顿程序员必读书单：https://github.com/silently9527/ProgrammerBooks
微信公众号：贝塔学Java