1. 概论
前面说到了图这种非线性的数据结构，并且我使用了代码，简单演示了图是如何实现的。今天就来看看基于图的两种搜索算法，分别是广度优先搜索和深度优先搜索算法，这两个
算法都十分的常见，在平常的面试当中也可能遇到。
在图上面的搜索算法，其实主要的表现形式就是从图中的一个顶点，找到和另一个顶点之间的路径，而两种搜索算法，都是解决这个问题的。
2. 广度优先搜索
广度优先搜索的基本思路就是从一个顶点出发，层层遍历，直到找到目标顶点，其实这样搜索出来的路径也就是两个顶点之间的最短距离。如下图所示，例如要搜索出顶点 s -> t 的路径，搜索的方式就是这样的：
其中黄色的线条表示搜索的节点，数字 1、2、3、4 表示搜索的次序，广度优先搜索的原理看起来十分的简单，但是它的代码实现还是稍微有点难的，先来看看整体的代码实现，然后再具体讲解一下：
public class BFS { /** * 广度优先搜索算法 * @param graph 图 * @param s 搜索的起点（对应图中的一个顶点） * @param t 搜索的终点 */ public static void bfs(Graph graph, int s, int t){ if (s == t) return; //获得图的顶点个数 int vertex = graph.getVertex(); //获取存储图顶点的列表 LinkedList<Integer>[] list = graph.getList(); //如果某个顶点已经被访问，则设置为true boolean[] visited = new boolean[vertex]; visited[s] = true; //队列，存储的是已经被访问，但是其相连的顶点还没有被访问的顶点 Queue<Integer> queue = new LinkedList<>(); queue.add(s); //记录搜索的路径 int[] path = new int[vertex]; for (int i = 0; i < vertex; i++) { path[i] = -1; } while (queue.size() != 0){ int w = queue.poll(); for (int i = 0; i < list[w].size(); i++) { int q = list[w].get(i); if (!visited[q]){ path[q] = w; if (q == t){ print(path, s, t); return; } visited[q] = true; queue.add(q); } } } } //递归打印 s-t 的路径 private static void print(int[] prev, int s, int t){ if (prev[t] != -1 && t != s){ print(prev, s, prev[t]); } System.out.print(t + " "); } }
程序中有三个辅助的变量：
一是 boolean[] visited ，这个数组表示如果已经被访问，则设置为 true，例如顶点 s，是最开始被访问的，直接设置为 true。
二是有一个队列 queue，它表示的是，一个顶点已经被访问，但是其相邻的顶点还没有被访问的顶点。例如顶点 s，它自己被访问了，但是和它相邻的两个顶点还没有被访问，因此直接被添加到了队列当中。
三是数组 path，它表示一个顶点是被哪个顶点所访问的，数组下标表示的是顶点，对应存储的是由谁所访问。这个逻辑在代码中的体现便是 path[q] = w 这一行。最后，这个数组中存储的便是搜索的路径，需要递归打印出来。
3. 深度优先搜索
再来看看深度优先搜索，这种搜索的基本思路就是：从起始顶点出发，任意遍历顶点，如果走不通，则回退一个顶点，然后换一个顶点继续遍历，知道找到目标顶点。像下图这样：
图中从顶点 s 出发，蓝色的表示前进的顶点，红色的表示后退一个顶点，直到找到目标顶点 t，相信你可以看出来，这样搜索出来的路径其实并不是 s 到 t 的最短路径，而是任意的一条路径。
深度优先的代码实现：
public class DFS { //判断是否找到了目标顶点 private static boolean found = false; public static void dfs(Graph graph, int s, int t){ int vertex = graph.getVertex(); boolean[] visited = new boolean[vertex]; int[] path = new int[vertex]; for (int i = 0; i < vertex; i++) { path[i] = -1; } LinkedList<Integer>[] list = graph.getList(); recursionDfs(list, s, t, visited, path); print(path, s, t); } //递归遍历 private static void recursionDfs(LinkedList<Integer>[] list, int w, int t, boolean[] visited, int[] path){ if (found) return; visited[w] = true; if (w == t){ found = true; return; } for (int i = 0; i < list[w].size(); i++) { int q = list[w].get(i); if (!visited[q]){ path[q] = w; recursionDfs(list, q, t, visited, path); } } } private static void print(int[] path, int s, int t){ if (path[t] != -1 && t != s){ print(path, s, path[t]); } System.out.print(t + " "); } }
变量 boolean[] visited 和广度优先搜索一样，都是表示访问过的节点设置为 true，path 数组表示访问的路径。
最后，总结一下，广度和深度优先搜索，都是比较暴力的搜索方式，没有什么优化，层层遍历或者一路递归，所以不难看出，这两个算法的时间复杂度接近 O(n)，空间复杂度也是 O(n)，还是稍微有点高的，所以这两种搜索算法适用于图上的顶点数据不太多的情况。
