广度优先遍历，也称为广度优先搜索。简称BFS
类似于二叉树的层序遍历
-
算法准备
a. 记录是否遍历过的数组
b. 邻接点的队列
-
算法思路（递归）
a. 从某顶点开始
b. 将该顶点记录，并输出值
c. For循环查找该顶点的邻接点。将邻接点下标添加到队列中
d. while循环，循环条件为队列不为空
e. 移出队首顶点下标
f. 如果没访问过则递归该邻接点
public class Graph> {
// 顶点数组
private T[] vertexs;
// 邻接表元素数组
private VertexNeighborNode[] neighborArray;
// 邻接矩阵
private int[][] matrix;
// 泛型对象的类文件
private Class Class;
// 顶点数量
private int size;
/**
* 广度优先遍历方法（递归）
*/
public void bredthFirst() {
// 建立记录数组
boolean[] isVisited = new boolean[size];
// 创建队列
LinkedList queue = new LinkedList();
// 广度优先遍历方法实现，从第一个开始
bredthFirst(isVisited, queue, 0);
}
/**
* 广度优先算法遍历方法实现
* @param isVisited 记录数组
* @param queue 队列
* @param i 开始顶点
*/
private void bredthFirst(boolean[] isVisited, LinkedList queue,
int i) {
// 将当前顶点设置为已遍历
isVisited[i] = true;
System.out.println("第" + i + "个顶点被访问了：" + vertexs[i]);
// 循环将该顶点的出度顶点下标添加到队列中
for (int j = 0; j < size; j++) {
// 出度顶点判断，不为自己 并且 相连 并且没有访问过
if (matrix[i][j] != 0 && matrix[i][j] != NO_LINK && !isVisited[j]) {
// 添加到队列
queue.offer(j);
}
}
// 如果队列不为空则循环
while (!queue.isEmpty()) {
// 将顶点下标从队首弹出
int weight = queue.poll();
// 如果该顶点没访问过
if (!isVisited[weight]) {
// 递归广度遍历该方法
bredthFirst(isVisited, queue, weight);
}
}
}
}
