前言：

图这种数据结构经常用于表示一个社交网络，在社交网络中有一个六度分割理论，简单来说就是你与世界上的另一个人间隔的关系不会超过六度，也就是说平均只需要六步就可以联系到任何两个不认识的人。而深度优先算法和广度优先算法就是基于图这种数据结构的一种搜索算法思想。

搜索算法：

图上的搜素算法，最直接的理解是，在图中找出一个顶点出发，到另一个顶点的路径，其中广度优先算法和深度优先算法就是最简单、暴力的搜索算法。

邻接表的代码实现：


public class Graph { // 无向图private int v; // 顶点的个数private LinkedList<Integer> adj[]; // 邻接表public Graph(int v) {this.v = v;adj = new LinkedList[v];for (int i=0; i<v; ++i) {adj[i] = new LinkedList<>();}}public void addEdge(int s, int t) { // 无向图一条边存两次adj[s].add(t);adj[t].add(s);}
}

广度优先搜索算法

广度优先搜索算法简称BFS。广度优先简单来讲，就是一种层层递进地毯式的搜索策略，即线查找离起始顶点最近的，然后是次进的，依次往外搜索。示意图如下：

BFS的代码实现，其中S表示起始顶点，t表示终止顶点。我们搜索一条从s到t的路径，也就是需要求得一条从s到t的最短路径。


public void bfs(int s, int t) {if (s == t) return;boolean[] visited = new boolean[v];visited[s]=true;Queue<Integer> queue = new LinkedList<>();queue.add(s);int[] prev = new int[v];for (int i = 0; i < v; ++i) {prev[i] = -1;}while (queue.size() != 0) {int w = queue.poll();for (int i = 0; i < adj[w].size(); ++i) {int q = adj[w].get(i);if (!visited[q]) {prev[q] = w;if (q == t) {print(prev, s, t);return;}visited[q] = true;queue.add(q);}}}
}private void print(int[] prev, int s, int t) { // 递归打印s->t的路径if (prev[t] != -1 && t != s) {print(prev, s, prev[t]);}System.out.print(t + " ");
}

visited 是用来记录已经被访问的顶点，用来避免顶点被重复访问。如果顶点 q 被访问，那相应的 visited[q]会被设置为 true。

queue 是一个队列，用来存储已经被访问、但相连的顶点还没有被访问的顶点。因为广度优先搜索是逐层访问的，也就是说，我们只有把第 k 层的顶点都访问完成之后，才能访问第 k+1 层的顶点。当我们访问到第 k 层的顶点的时候，我们需要把第 k 层的顶点记录下来，稍后才能通过第 k 层的顶点来找第 k+1 层的顶点。所以，我们用这个队列来实现记录的功能。

prev 用来记录搜索路径。当我们从顶点 s 开始，广度优先搜索到顶点 t 后，prev 数组中存储的就是搜索的路径。不过，这个路径是反向存储的。prev[w]存储的是，顶点 w 是从哪个前驱顶点遍历过来的。比如，我们通过顶点 2 的邻接表访问到顶点 3，那 prev[3]就等于 2。为了正向打印出路径，我们需要递归地来打印，你可以看下 print() 函数的实现方式。

广度优先搜索的分解图如下：

这个时候，每个顶点都要进出一遍队列，每个边也都会被访问一次，所以，广度优先搜索的时间复杂度是 O(V+E)，其中，V 表示顶点的个数，E 表示边的个数。当然，对于一个连通图来说，也就是说一个图中的所有顶点都是连通的，E 肯定要大于等于 V-1，所以，广度优先搜索的时间复杂度也可以简写为 O(E)。广度优先搜索的空间消耗主要在几个辅助变量 visited 数组、queue 队列、prev 数组上。这三个存储空间的大小都不会超过顶点的个数，所以空间复杂度是 O(V)。

深度优先搜索算法

深度优先搜索算法简称DFS，最直观的例子是走迷宫。

假设你在某个迷宫的入口，你想要找到出口，遇见岔路口，任意选择一条路走，如果走不通，则回到上一个岔路口选择另外一条路继续走，这种走法就是一种深度优先搜索策略。

深度优先算法的示意图：

实际上，深度优先搜索用的是一种比较著名的算法思想，回溯思想。这种思想解决问题的过程，非常适合用递归来实现。

代码实现


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);}}
}

问题：如何找出社交网络中某个用户的三度好友关系？

这个问题可以用图得广度优先搜索算法，首先，遍历与起始顶点最近的一层顶点，也就是用户的一度好友，然后再遍历与用户距离的边数为 2 的顶点，也就是二度好友关系，以及与用户距离的边数为 3 的顶点，也就是三度好友关系。

总结：

广度优先搜索算法和深度优先搜索是图的两种最常用、最基本的搜索算法也叫暴力搜索算法，所以仅适用于数据量大，图不大的搜索。

广度优先搜索，通俗的理解就是，地毯式层层推进，从起始顶点开始，依次往外遍历。广度优先搜索需要借助队列来实现，遍历得到的路径就是，起始顶点到终止顶点的最短路径。深度优先搜索用的是回溯思想，非常适合用递归实现。换种说法，深度优先搜索是借助栈来实现的。在执行效率方面，深度优先和广度优先搜索的时间复杂度都是 O(E)，空间复杂度是 O(V)。