检索算法是在具有某种数据结构的基础上起作用的算法，大多数检索算法都是基于“图”这一数据结构。 这是因为图的表现力很强，检索中涉及的场景大部分都可以抽象为“图”。
所谓“检索”，最直接的理解是从图中寻找从一个顶点到另一个顶点的路径。 根据需求和场景的不同，应对有不同的算法。
图中，邻接表和邻接矩阵这次用邻桌保存图，用无向图举例说明。
public class Graph{ //有向图private int v； //顶点数private LinkedListInteger adj[]； //邻表publicgraph(intv ) ) { this.v=v； adj=new LinkedList[v]； for(intI=0； ； I ) { adj[i]=new LinkedList (； }publicvoidaddedge(ints，int t ) ) adj[s].add ) t； adj[t].add(s )； }广度优先搜索广度优先搜索(Breadth First Search，BFS )从直观上来看，实际上是先寻找最接近开始顶点s的，再寻找最近的，直到找到最后的顶点t为止依次向外搜索的地面搜索策略。 实际上，通过广度优先搜索发现的从起点到终点的路径也是从顶点s到顶点t的最短路径。
幅度优先搜索的原理非常简单，但代码实现相对来说并不简单。 首先，我们来看看如何实现广度优先搜索。 让我们看看代码。 其中，s表示开始顶点编号，t表示结束顶点编号。 我们搜索从s到t的路径。
公共void bfs (ints，int t ) ) if ) s==t ) return； boolean[] visited=new boolean[v]； visited[s]=true； queueintegerqueue=new linked list (； queue.add(s； int[] prev=new int[v]； for(intI=0； ； I ) { prev[i]=-1； }while(queue.size ) )！=0() { int w=queue.poll )； for(intI=0； i adj[w].size； I ) (intq=adj[w].get ) I； if (！ visited[q]}{prev[q]=w； if(q==t ) print ) prev，s，t )； 返回； } visited[q]=true； queue.add(q )； }}}privatevoidprint(int[]prev，int s，int t ) ) if ) prev[t]！=-1 t！=s ) {print(prev，s，prev[t]； }system.out.println(t ' )； }宽度优先搜索代码的实现包括三个重要的辅助变量： visited、queue和prev。
visited数组用于记录已经访问的顶点，并防止再次访问这些顶点。 如果顶点q已经被访问，则visited[q]将被设置为true。
queue是队列，队列具有先进先出的特点，队列用于许多分层遍历需求。 由于宽度优先搜索逐层访问顶点，所以我们只能在访问了所有第k层的顶点后访问第k 1层的顶点。 访问最后一个k层的顶点时，需要记录k层的顶点，然后从k层的顶点开始找到第k 1层的顶点。
prev用于记录探索路径，在从顶点探索到顶点t之后，在prev排列中保存从顶点s到顶点t的路径。 但是，这条路径会以相反的方向保存。 prev[w]存储顶点w的前驱节点，即路径的前面的顶点。 正向路径(即代码中的print ) )函数实现的功能必须递归输出。
既然掌握了广优先搜索算法的原理，广优先搜索的时间、空间复杂度是多少呢？ 在最坏的情况下，结束顶点t离开始顶点s很远，为了找到需要遍历完整的图。 此时，各顶点出入矩阵，分别为
边也都会被访问一次，所以，广度优先搜索的时间复杂度是 O(V+E)，其中，V 表示顶点的个数，E 表示边的个数。当然，对于一个连通图来说，也就 是说一个图中的所有顶点都是连通的，E 肯定要大于等于 V-1，所以，广度优先搜索的时间 复杂度也可以简写O(E)。 广度优先搜索的空间消耗主要在几个辅助变量 visited 数组、queue 队列、prev 数组上。 这三个存 储空间的大小都不会超过顶点的个数，所以空间复杂度是 O(V)深度优先搜索（DFS） 深度优先搜索（Depth-First-Search），简称 DFS。最直观的例子就是“走迷宫”。 假设你站在迷宫的某个岔路口，然后想找到出口。你随意选择一个岔路口来走，走着走着发 现走不通的时候，你就回退到上一个岔路口，重新选择一条路继续走，直到最终找到出口。 这种走法就是一种深度优先搜索策略。 走迷宫的例子很容易能看懂，我们现在再来看下，如何在图中应用深度优先搜索，来找某个 顶点到另一个顶点的路径。你可以看我画的这幅图。搜索的起始顶点是 s，终止顶点是 t，我们希望在图中寻找一条从 顶点 s 到顶点 t 的路径。如果映射到迷宫那个例子，s 就是你起始所在的位置，t 就是出 口。 我用深度递归算法，把整个搜索的路径标记出来了。这里面实线箭头表示遍历，虚线箭头表 示回退。从图中我们可以看出，深度优先搜索找出来的路径，并不是顶点 s 到顶点 t 的最 短路径
实际上，深度优先搜索用的是一种比较著名的算法思想，回溯思想。这种思想解决问题的过 程，非常适合用递归来实现。回溯思想我们后面会有专门的一节来讲，我们现在还回到深度 优先搜索算法上。 我把上面的过程用递归来翻译出来，就是下面这个样子。我们发现，深度优先搜索代码实现 也用到了 prev、visited 变量以及 print() 函数，它们跟广度优先搜索代码实现里的作用是 一样的。不过，深度优先搜索代码实现里，有个比较特殊的变量 found，它的作用是，当 我们已经找到终止顶点 t 之后，我们就不再递归地继续查找了。 boolean found = false; public void dfs(int s,int t){ found = false; boolean[] visited = new boolean[v]; int[] prev = new int[v]; for(int i = 0;i < v;i++){ prev[i] = -1; } recurDfs(s,t,visited,prev); print(prev,s,t); } private void recurDfs(int w,int t,boolean[] visited,int[] prev){ if(found == true) return; visited[w] = true; if(w == t){ found = true; return; } for(int i = 0;i < adj[w].size();i++){ int q = adj[w].get(i); if(!visited[q]){ prev[q] = w; recurDfs(q,t,visited,prev); } } } 理解了深度优先搜索算法之后，我们来看，深度度优先搜索的时、空间间复杂度是多少呢？ 从我前面画的图可以看出，每条边最多会被访问两次，一次是遍历，一次是回退。所以，图 上的深度优先搜索算法的时间复杂度是 O(E)，E 表示边的个数。 深度优先搜索算法的消耗内存主要是 visited、prev 数组和递归调用栈。visited、prev 数 组的大小跟顶点的个数 V 成正比，递归调用栈的最大深度不会超过顶点的个数，所以总的 空间复杂度就是 O(V)。