换人！小编连怎么能快速找到女朋友都不知道
在数据结构中对广撒网有一种类似的定义，叫做广度优先搜索（Breadth-First-Search），简称BFS。是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次进的，依次往外搜索。
先把一个顶点附近的顶点查找一遍，然后再从它附近的顶点开始查找，重复一样的操作。如上图所示，先从A点出发，查找离A点最近的B和C，如果这两个不是想要的节点，那么就以B和C为起点，查找与B和C相连接的顶点。广度优先搜索策略得到的路径是起始点到终点的最短路径。
为什么说广度优先搜索策略找到的路径是最短路径呢？最简单的一种解释方式，想想圆规画圆，以A点为顶点，不断的增加圆的半径。
这个像不像你先跟某寝室的女孩子小A相处，然后发现小A不跟你玩，然后你开始通过A对她的室友下手，emmm……最后得出结论，渣男实锤了。我们下次还是聊点专一的操作吧。
编程逻辑
- 从一个顶点 A 出发，查找与 A 相通的其它顶点
- 判断查找的顶点是否访问过，访问过则直接跳过
- 如果顶点没有访问过，判断顶点是否为要查找的顶点
- 如果是不是要查找到顶点，则标记顶点为已访问的状态
- 把刚刚更改状态的顶点放入待查找顶点集合
- 接着寻找顶点 A 的相通顶点，重复 2 ~ 5 的步骤
- 当 A 的通顶点都遍历一遍时，从待查找顶点集合中取出一个元素，重复上述 1 ~ 6 的操作
代码实现
import java.util.LinkedList; import java.util.Queue; /** * 广度优先搜索 * * @since 2021-03-18 */ public class GrapBfs { // 顶点的个数 private int v; // 邻接表 private LinkedList<Integer>[] adj; public GrapBfs(int v) { this.v = v; adj = new LinkedList[v]; for (int i = 0; i < v; i++) { adj[i] = new LinkedList<>(); } visited = new boolean[v]; pre = new Integer[v]; for (int i = 0; i < v; i++) { pre[i] = -1; } } /** * 一条边的两个顶点，表示两个边相连 * * @param s 顶点 * @param t 顶点 */ public void addEdge(int s, int t) { adj[s].add(t); adj[t].add(s); } public int getV() { return v; } public LinkedList<Integer>[] getAdj() { return adj; } // 存放接下来需要查找其周边顶点的顶点 Queue<Integer> queue = new LinkedList<>(); // 记录顶点是否已经被访问过 boolean[] visited; // 记录顶点的前一个顶点 Integer[] pre; /** * 广度优先搜索 * * @param start 起始位置 * @param end 结束位置 */ public void bfs(int start, int end) { if (start == end) { return; } queue.offer(start); Integer present; visited[start] = true; while (!queue.isEmpty()) { present = queue.poll(); LinkedList<Integer> linkedList = adj[present]; for (Integer nextVertex : linkedList) { if (visited[nextVertex]) { continue; } visited[nextVertex] = true; pre[nextVertex] = present; if (nextVertex == end) { print(pre, nextVertex); System.out.println(end); return; } queue.offer(nextVertex); } } } /** * 输出查找的路径 * * @param pre 记录顶点前一个顶点的数组 * @param nextVertex 当前顶点的下一个顶点 */ private void print(Integer[] pre, Integer nextVertex) { if (pre[nextVertex] == -1) { return; } print(pre, pre[nextVertex]); System.out.print(pre[nextVertex]); } public static void main(String[] args) { GrapBfs grap = new GrapBfs(9); grap.addEdge(1, 2); grap.addEdge(1, 4); grap.addEdge(2, 3); grap.addEdge(2, 5); grap.addEdge(3, 6); grap.addEdge(4, 5); grap.addEdge(5, 6); grap.addEdge(5, 7); grap.addEdge(6, 8); grap.addEdge(7, 8); grap.bfs(1, 7); } }
复杂度
V 表示顶点的个数，E 表示边的个数
广度优先搜索的时间复杂度为O(E)，空间复杂度为O(V)
最坏的情况下，我们从一个顶点出发，需要遍历整个图才能找到需要查找的顶点，此时每个顶点都要进出遍集合，每个边被访问一边，所以时间复杂度为O(V+E)
对一个连通图来说，也就是一个图中的所有顶点都是连通的，E 肯定要大于等于 V-1，所以时间复杂度简写为O(E)
空间消耗主要有是待访问顶点的集合，标记已访问的集合。每一块需要的口存储空间大小都不会超过顶点的个数，所以空间复杂度为O(V)
