广度优先搜索(breadth-first search，BFS)

本文主要是介绍广度优先搜索(breadth-first search，BFS)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

广度优先搜索(breadth-first search，BFS)

应用场景：到X的最短路径

原理：搜索范围从起点向外延伸，先查一度关系，再查二度关系，以此类推

这样不仅能找到A到B的路径，而且找到的还是最短的路径

注意：只有按关系层级顺序查找才能找到最短路径

使用的数据结构：

队列(Queue)，先进先出(FIFO)

散列表(Map)，用来映射元素下一层级关联的元素，在下面例子中对应某个人的朋友们

运行时间：O(V+E) V：边数 E：顶点数
整个关系网中，你将沿着每条边前进，所有运行时间最少为O(边数)

你要把需要检查的人加入到队列中，每个人需要O(1)，每个人都需要这样做，一共O(人数)

即广度优先搜索的运行时间为O(人数+边数) 人数：顶点数V(vertice)

样例：找出下面关系网中距离最近的销售商(名字结尾为m的人)

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iZ0SLUmX-1647241989039)(D:\Markdown图片\image-20220314150905396.png)]$

private static Set<String> set = new HashSet<>();
private static void breadthFirstSearch(Map<String, Object> map, Queue<String> queue) {while (queue.size() > 0) {// 获取队列头一个元素并出队String first = queue.remove();// 没有被检查过才可以进行检查if (!checkRepeat(first)) {// 判断是否是所要元素if(personIsSeller(first)) {System.out.println(first + "是售货商!");// 找到了售货商 结束程序return;}// 不是的话把它的朋友加入到队列尾部else {if (map.get(first) instanceof String[]) {String[] firends = (String[]) map.get(first);queue.addAll(Arrays.asList(firends));} else if (map.get(first) instanceof String) {String firend = (String) map.get(first);queue.add(firend);}}}}
}

判断这个人是否是销售商

private static boolean personIsSeller(String person) {// 把每个检查的元素放入Set集合中set.add(person);// substring(int index)方法去截字符串位置index及以后的所有字符串，// substring(int from ,int to)方法是前闭后开的，即[from,to),可以理解为[from,to-1]if (person.substring(person.length()-1).equals("m")) {return true;}return false;
}

判断这个人有没有被检查过

// 你的朋友也可能是你朋友的朋友 可能
// 这里要把所有检查过的人添加到Set集合中，以免重复检查，如果是双向图可能会造成无限循环
public static boolean checkRepeat(String person) {if (set.contains(person)) {System.out.println(person + "重复了!");return true;}return false;
}

Test

public static void main(String[] args) {Map<String, Object> map = new HashMap<>();String[] you = {"alice","bob","claire"};map.put("you", you);String[] bob = {"anuj","peggy"};map.put("bob", bob);map.put("alice", "peggy");String[] claire = {"thom", "jonny"};map.put("claire", claire);map.put("anuj", null);map.put("peggy", null);map.put("thom", null);map.put("jonny", null);// 把第一层级的朋友加入队列Queue<String> queue = new LinkedList<>();queue.addAll(Arrays.asList(you));breadthFirstSearch(map, queue);
}