广度优先遍历思路:
还是以之前深度优先遍历的图为例,如下:
A B C D E F G H
A[0, 1, 0, 0, 0, 1, 0, 1]
B[1, 0, 1, 0, 0, 0,...1, 0]
F[1, 0, 0, 0, 0, 0, 1, 0]
G[0, 1, 0, 0, 1, 1, 0, 0]
H[1, 0, 0, 1, 0, 0, 0, 0]
所谓广度优先,就类似二叉树的层序遍历...所在行所有未被访问过的1对应的顶点,发现没有;
接着搞A的第三个邻接顶点H所在的行,输出H所在行所有未被访问过的1对应的顶点,即D;
A所在的行搞完了,就搞B、D、E……H所在的行,重复上面的操作,最终的遍历结果是...UnDirectionGraph {
private List vertexList; // 存放顶点
private int[][] edges; // 邻接矩阵,存放图的边...vertexCount][vertexCount];
this.isVisited = new boolean[vertexCount];
}
/**
* 构建无向图