宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
宽度优先搜索算法类似于一个分层搜索的过程，宽度优先搜索算法需要一个队列以保持访问过顶点的顺序，以便按这个顺序来访问这些顶点的邻接顶点。
思路：依次访问当前顶点的邻接顶点，并按访问顺序将这些邻接顶点存储在队列中，当当前顶点的所有邻接顶点都被访问后，从队列中弹出一个顶点，以该顶点为当前顶点继续该步骤，直到所有顶点都被访问过。
依次访问当前顶点的所有邻接顶点，并把这些邻接顶点按访问顺序存储在队列中
当前顶点没有未访问的邻接顶点，从队列中弹出一个顶点，以该弹出顶点继续访问未访问的邻接顶点
注意，虽然图中的顶点都已经访问过了，但还是要等队列中的所有顶点弹出访问后，算法才结束
下面时宽度优先搜索的过程动画
代码演示
public void bfs(){ visited = new boolean[vertexes.size()]; 以在集合中下标为0的顶点，进行广度优先搜索 bfs(visited, 0); } /** * 广度优先搜索 * @param visited * @param row */ public void bfs(boolean[] visited, int row){ //创建队列，存储遍历邻接顶点的顺序 LinkedList queue = new LinkedList(); //输出当前顶点 System.out.print(vertexes.get(row) + " -> "); //将当前顶点设为已访问 visited[row] = true; //将当前顶点加入队列中 queue.add(row); //当队列不为空时，即有未搜索的邻接顶点，进行搜索 while (!queue.isEmpty()){ //按顺序从队列中弹出邻接顶点下标 int last = (Integer)queue.removeFirst(); //获取该弹出顶点的邻接顶点下标 int index = getFirstNeighbor(last); //当弹出顶点有邻接顶点时，进行广度搜索 while(index != -1){ //当邻接顶点未访问时 if(visited[index] != true){ //输出该邻接顶点 System.out.print(vertexes.get(index) + " -> "); //把该邻接顶点设为已访问 visited[index] = true; //将该邻接顶点加入队列 queue.addLast(index); } //继续寻找弹出顶点的另一个邻接顶点 index = getNeighbor(last, index); } } }