static int[][] nums = { { 0 , 1 , 0 , 0 , 0 , 0 , 0, 1 , 0}, { 1 , 0, 1 ,0 , 1 , 0 , 0 , 0 , 0}, { 0 , 1 , 0 , 1 , 0 ,0 , 0 , 0 , 0}, { 0 , 0 , 1 , 0 , 1 , 1 , 0 , 0 ,0}, { 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0}, { 0 , 0 , 0 , 1 , 0 , 0 , 1 , 1 , 0}, { 0 , 0 , 0 , 0 , 0 , 1, 0 , 0 , 0}, { 1 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 1}, { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0} }; static String res[] = {"1","2","3","4","5","6","7","8","9" };
广搜遍历过程
和深搜不同广搜会沿着树的高度和宽度对节点进行依次遍历
从树的根节点1开始，会发现1的子节点有2、8两个子节点，进程会先对这两个节点进行访问然后再访问其的子节点
对2、8完成访问之后进行则会探寻这两个节点的子节点并对其进行遍历，可以从图中看出他们的子节点有3、5、6、9
然后进程对着4个节点完成遍历之后会再次探寻其的子节点可以看出只有4和7了且无子节点
在对4和7完成遍历之后整个进程也就随之结束了。
package test; import java.util.LinkedList; import java.util.Queue; public class bfs { // 构造图的边 private int[][] edges = { { 0 , 1 , 0 , 0 , 0 , 0 , 0, 1 , 0}, { 1 , 0, 1 ,0 , 1 , 0 , 0 , 0 , 0}, { 0 , 1 , 0 , 1 , 0 ,0 , 0 , 0 , 0}, { 0 , 0 , 1 , 0 , 1 , 1 , 0 , 0 ,0}, { 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0}, { 0 , 0 , 0 , 1 , 0 , 0 , 1 , 1 , 0}, { 0 , 0 , 0 , 0 , 0 , 1, 0 , 0 , 0}, { 1 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 1}, { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0} }; // 构造图的顶点 private String[] vertexs = {"1","2","3","4","5","6","7","8","9"}; // 记录被访问顶点 private boolean[] verStatus; // 顶点个数 private int vertexsNum = vertexs.length; // 广搜 private void BFS() { verStatus = new boolean[vertexsNum]; Queue<Integer> temp = new LinkedList<Integer>(); //遍历每个节点 for (int i = 0; i < vertexsNum; i++) { //判断当前节点是否被访问过 if (!verStatus[i]) {//如果没有被访问的话则将其加入队列 System.out.print(vertexs[i] + " "); verStatus[i] = true; temp.offer(i); while (!temp.isEmpty()) { //将最先进入队列的节点移除 int j = temp.poll(); //广度搜索子节点 for (int k = firstAdjvex(j); k >= 0; k = nextAdjvex(j, k)) { if (!verStatus[k]) { System.out.print(vertexs[k] + " "); verStatus[k] = true; temp.offer(k); } } } } } } // 返回与i相连的第一个顶点 private int firstAdjvex(int i) { for (int j = 0; j < vertexsNum; j++) { if (edges[i][j] > 0) { return j; } } return -1; } // 返回与i相连的下一个顶点 private int nextAdjvex(int i, int k) { for (int j = (k + 1); j < vertexsNum; j++) { if (edges[i][j] > 0) { return j; } } return -1; } // 测试 public static void main(String args[]) { new bfs().BFS(); } }
输出结果：
1 2 8 3 5 6 9 4 7
