（二十）广度优先和深度优先搜索
01
—
广度优先
什么是广度优先算法：
让我们打个比方：比如你是一个果农🥭，
那么你可以继续在朋友的朋友中寻找
最后终于寻找到了芒果经销商。
其实很简单这种算法遍历你的整个人际关系网，直到找到经销商就是广度优先搜索
广度优先搜索如下图，会先在一度关系找，然后是二度关系，这样层层递进。
广度优先搜索可以解决两类问题
第一类是：从A节点触发有前往B节点的路径么（在你的关系网中有芒果经销商吗）？
第二类是：从A节点触发前往B节点的哪条路径最短（哪个芒果经销商与我的关系最近）
广度优先的代码实现
例如要对顶点A进行广度优先遍历，寻找到B的最短路径
步骤如下：
首先需要一个队列Q，把A的一度好友放入队列中
再需要一个集合S，用于存放已经访问过的元素，避免造成循环访问的情况
对Q进行遍历，队首的元素H不在S中，并且不是B，则遍历H的一度好友放入到Q中，以此循环遍历
代码实现：
public class MyGraph {private LinkedList<Integer> adj[];private int v; //顶点的个数public MyGraph(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 e) {adj[s].add(e);}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){Integer 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 + " ");}}
广度优先算法的时间复杂度比较好算，就是点的个数加上边的个数
O(V+E)，由于边的个数会远大于点的个数，因此可以看成时间复杂度是O(E)
02
—
深度优先
深度优先算法如同走迷宫，我们随意选择一个岔路来走
当发现走不通了，再退回到上一个岔路口，重新选择一条路走
直到找到最后的出口。
如图：
代码：
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)
03
—
总结
广度优先：是从起始点开始，地毯式搜索，需要借助队列来实现。
深度优先：需要回溯思想，借助递归来实现。
二者时间复杂度都是O(E)