就这？也能获得翠花的联系方式？
这又是一个夜黑风高的晚上，豆哥在路上看到一个漂亮的小姐姐翠花，随后一路尾随（真猥琐），最终发现小姐姐匆匆忙忙的进了隔壁班，可惜豆哥没有隔壁班的熟人，这时候该怎么办呢?
机智的豆找朋友 小A 帮忙，小A 跟给你推荐了小B，你发现 小B 跟翠花没有交集，帮不上忙啊，然后豆哥又回去找小A，一脸生无可恋，让 小A 再给推荐一个人，直到最后拿到了翠花的联系方式，从此走上人生巅峰 翠花把豆哥拉黑删除一顿操作，全剧终。这就是 深度优先搜索（Depth-First-Search）,简称 DFS。
深度优先搜索使用了回溯思想， 算是比较暴力的一种方式，但是找出来的路径，并一定是最短路径。
另外聊一个有意思的理论——六度分离理论，“你和任何一个陌生人之间所间隔的人不会超过五个，也就是说，最多通过五个人你就能够认识任何一个陌生人。” 想想这是为什么呢？·
编程逻辑
- 从一个顶点 A 出发，然后查找跟它相通的顶点
- 当发现第一个想通的顶点 B 时，就继续查找顶点 B 想通的顶点
- 如果发现 B 没有相通的顶点，或者与 B 相通的顶点都被访问过时，则回退到顶点 A
- 查找下一个与 A 相通的顶点，然后重复上述操作
- 结束条件为找到指定的顶点或者所有顶点都被遍历一遍
代码实现
import java.util.LinkedList; /** * 深度优先搜索 */ public class GrapDfs { // 顶点的个数 private int v; // 邻接表 private LinkedList<Integer>[] adj; // 标记顶点是否被访问 private boolean[] visited; // 记录一个顶点的前一个顶点 private Integer[] pre; // 标记是否已经找到 private boolean found = false; public GrapDfs(int v) { this.v = v; adj = new LinkedList[v]; visited = new boolean[v]; pre = new Integer[v]; for (int i = 0; i < v; i++) { adj[i] = new LinkedList<>(); pre[i] = -1; } } public void add(int a, int b) { adj[a].add(b); adj[b].add(a); } public void dfs(int start, int end) { // 已经找到路径 if (found) { return; } if (start == end) { print(pre, end); System.out.println(end); found = true; return; } visited[start] = true; int size = adj[start].size(); for (int i = 0; i < size; i++) { Integer next = adj[start].get(i); if (!visited[next]) { pre[next] = start; dfs(next, end); } } } private void print(Integer[] pre, Integer end) { if (pre[end] == -1) { return; } int p = pre[end]; print(pre, p); System.out.print(p); } public static void main(String[] args) { GrapDfs grap = new GrapDfs(9); grap.add(1, 2); grap.add(1, 4); grap.add(2, 3); grap.add(2, 5); grap.add(3, 6); grap.add(4, 5); grap.add(5, 6); grap.add(5, 7); grap.add(6, 8); grap.add(7, 8); grap.dfs(1, 7); } }
复杂度
V 表示顶点的个数，E 表示边的个数
广度优先搜索的时间复杂度为O(E)，空间复杂度为O(V)
深度优先搜索策略中，加入我们使用栈存放顶点，每个顶点进栈出栈一次，相当于每条边被访问两次，时间复杂度即为O(E)
内存消耗主要是标记数组，方法调用栈，大小跟顶点的个数成正比，方法调用栈的最大深度也不会超多顶点的个数，所以总的空间复杂度为O(V)
