1. 广度优先遍历思路：
还是以之前深度优先遍历的图为例，如下：
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]
C[0, 1, 0, 1, 1, 0, 0, 0]
D[0, 0, 1, 0, 0, 0, 0, 1]
E[0, 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]
所谓广度优先，就类似二叉树的层序遍历，先搞完第一行，搞完第一行搞下一行。注意，这里的下一行，并不是第二行，而是看第一行顶点的第一个邻接顶点在第几行。具体步骤如下：
-
输出当前顶点A；
-
紧接者输出二维数组第一行所有
1对应的顶点，即B，F，H； -
第一行搞完，那就搞A的第一个邻接顶点B所在的行，输出B所在的行所有未被访问过的
1对应的顶点，即C，G； -
搞完A的第一个邻接顶点所在的行，就搞A的第二个邻接顶点F所在的行。输出F所在行所有未被访问过的
1对应的顶点，发现没有； -
接着搞A的第三个邻接顶点H所在的行，输出H所在行所有未被访问过的
1对应的顶点，即D； -
A所在的行搞完了，就搞B、D、E……H所在的行，重复上面的操作，最终的遍历结果是：
A -- B -- F -- H -- C -- G -- D -- E
2. 代码实现：
根据上面的思路，可以发现还是很简单的，完整代码如下：
public class UnDirectionGraph {
private List<String> vertexList; // 存放顶点
private int[][] edges; // 邻接矩阵，存放图的边
private boolean[] isVisited; // 顶点是否被访问
/**
* 构造器
*
* @param vertexCount
* 顶点的个数
*/
public UnDirectionGraph(int vertexCount, List<String> vertex) {
this.vertexList = vertex;
this.edges = new int[vertexCount][vertexCount];
this.isVisited = new boolean[vertexCount];
}
/**
* 构建无向图
*
* @param vertex1
* 顶点1
* @param vertex2
* 顶点2
* @param isConnected
* 顶点1和顶点2是否连通，0:未连通 1:已连通
*/
public void buildGraph(String vertex1, String vertex2, int isConnected) {
edges[vertexList.indexOf(vertex1)][vertexList.indexOf(vertex2)] = isConnected;
edges[vertexList.indexOf(vertex2)][vertexList.indexOf(vertex1)] = isConnected;
}
/**
* 打印邻接矩阵
*/
public void printGraph() {
for (int[] arr : edges) {
System.out.println(Arrays.toString(arr));
}
}
/**
* 查找顶点vertex的第一个邻接顶点
*
* @param vertex
*/
public int findFstNeighbor(String vertex) {
// 拿到vertex的索引
int vertexIndex = vertexList.indexOf(vertex);
// 遍历二维数组的第 vertexIndex 行
int[] arr = edges[vertexIndex];
for (int i = 0; i < arr.length; i++) {
// 如果arr[i] = 1，说明i对应的顶点就是vertex的邻接顶点
if (arr[i] == 1) {
return i;
}
}
return -1;
}
/**
* 根据vertex的前一个邻接顶点priorVertexIndex，找到下一个邻接顶点
*
* @param vertex
* @param priorVertexIndex
* @return
*/
public int findNeighborByPriorNeighbor(String vertex, int priorVertexIndex) {
// 拿到vertex的索引
int vertexIndex = vertexList.indexOf(vertex);
// 从(priorVertexIndex + 1)开始遍历二维数组的第 vertexIndex 行
int[] arr = edges[vertexIndex];
for (int i = priorVertexIndex + 1; i < arr.length; i++) {
if (arr[i] == 1) {
return i;
}
}
return -1;
}
public void bfs(String vertex, boolean[] isVisited) {
// 定义一个队列，用来该顶点的邻接顶点
Queue<String> queue = new LinkedList<>();
// 输出当前顶点
System.out.print(vertex + " ---> ");
// 标记当前顶点已访问
isVisited[vertexList.indexOf(vertex)] = true;
// 当前顶点也添加到队列中
queue.add(vertex);
// 队列不为空就循环，先处理完当前顶点
String currentVertex;
int neighborVetex;
while (!queue.isEmpty()) {
// 取出队列中的队头元素
currentVertex = queue.remove();
// 找到队头顶点的邻接顶点
neighborVetex = findFstNeighbor(currentVertex);
while (neighborVetex != -1) {
// 如果没被访问过，就访问，并且加到队列中
if (!isVisited[neighborVetex]) {
System.out.print(vertexList.get(neighborVetex) + " ---> ");
isVisited[neighborVetex] = true;
queue.add(vertexList.get(neighborVetex));
} else { // 否则就找邻接顶点后边那个邻接顶点
neighborVetex = findNeighborByPriorNeighbor(currentVertex, neighborVetex);
}
}
}
}
/**
* 广度优先遍历
*/
public void bfs() {
for (String str : vertexList) {
if (!isVisited[vertexList.indexOf(str)]) {
// 对每个顶点进行bfs
bfs(str, isVisited);
}
}
}
public static void main(String[] args) {
int vertexCount = 8;
List<String> vertexList = new ArrayList<>();
vertexList.add("A");
vertexList.add("B");
vertexList.add("C");
vertexList.add("D");
vertexList.add("E");
vertexList.add("F");
vertexList.add("G");
vertexList.add("H");
UnDirectionGraph graph = new UnDirectionGraph(vertexCount, vertexList);
graph.buildGraph("A", "B", 1);
graph.buildGraph("A", "H", 1);
graph.buildGraph("A", "F", 1);
graph.buildGraph("B", "G", 1);
graph.buildGraph("B", "C", 1);
graph.buildGraph("C", "D", 1);
graph.buildGraph("C", "E", 1);
graph.buildGraph("D", "H", 1);
graph.buildGraph("E", "G", 1);
graph.buildGraph("F", "G", 1);
graph.printGraph();
graph.bfs();
}
}
网友评论