广度优先搜索(BFS)
广度优先算法（BFS）又称宽度优先搜索，是指依次将与根节点路径长度（默认每条边长度相同）相同的点遍历，再遍历路径长度加一的点，直到遍历完整个图结束。
BFS在树中的应用
-
作用：BFS用于在树中搜索某个特定的数据。
-
方法：从根节点开始搜索，按层遍历整个树。一般使用队列（queue）结构存储层节点。
图1是BFS的效果演示图，每搜索到一个节点，判断是否符合要求，若不符合，则将它的孩子节点推入队列中，然后该节点出队列，直到队列为空时停止搜索，并返回搜索失败。
BFS在图中的应用
- 作用：搜索图中某个特定的数据，并记录distance
- 方法：从给定的起始节点开始，将与该点存在边的点放入队列，直到队列为空时结束搜索
- 不同：与树不同的是，不同的点可能会连接到同一个点，因此在图的BFS算法中，还要使用一个Set记录已经搜索过的点
性能分析
时间复杂度
在最差的情况下，BFS算法会搜索图中的每一个点，并且将每个点的边都加入队列中，因此时间复杂度最差为：O(|V| + |E|)，|V|是顶点的数量，|E|是边的数量
空间复杂度
对邻接表来说，邻接表存储所有的点，以及每个点的所有边，所以空间复杂度也是：O(|V| + |E|)，但是这个说法有争议，在Wikipedia上也给出了另一种：O(B^M)，其中B是最大分支系数，而M是树的最长路径长度
代码实现
/**
*本实例考虑的对象是树
*@param edges edges是邻接表
*@param val val是要查找的数据
*@return 返回所查找的点的深度
*/
public int bfs(ArrayList<LinkedList<String>> edges, String val) {
Deque<String> queue = new ArrayDeque<>();
//用一个map存放每个节点的深度
Map<String, Integer> map = new HashMap<>();
queue.addLast(root);
map.put(root, 0);
//设置队列的首元素
String first = root;
while(!queue.isEmpty()) {
first = queue.getFIrst();
if(first.equals(val)) {
return map.get(first);
}
//vertexes是点集，每个点在点集中的索引和它在遍集中的索引相同
int index = vertexes.indexOf(first);
int depth = map.get(first);
LinkedList<String> ll = edges.get(index);
ll.forEach(o -> {
queue.addLast(o);
map.put(o, depth + 1);
});
queue.removeFirst();
}
return -1;
}