共计 2478 个字符，预计需要花费 7 分钟才能阅读完成。
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)，还是稍微有点高的，所以这两种搜索算法适用于图上的顶点数据不太多的情况。
