图的广度优先搜索(Breadth-First Search,简称BFS)是一种用于遍历和搜索图的算法。它从图中的一个顶点开始,逐层地遍历其相邻顶点,并保持一个队列来存储待访问的顶点。BFS算法的核心思想是先访问离起始顶点最近的顶点,在此基础上逐层向外扩展,直到遍历完所有的顶点。
下面是使用Java实现图的广度优先搜索的示例代码:
import java.util.*;
public class GraphBFS {
private int V; // 顶点的个数
private LinkedList<Integer> adj[]; // 邻接表
public GraphBFS(int v) {
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
// 添加边
void addEdge(int v, int w) {
adj[v].add(w);
}
// 广度优先搜索
void BFS(int s) {
boolean visited[] = new boolean[V]; // 记录顶点是否被访问过
LinkedList<Integer> queue = new LinkedList<>(); // 使用队列保存待访问的顶点
visited[s] = true;
queue.add(s);
while (queue.size() != 0) {
s = queue.poll();
System.out.print(s + " ");
// 获取s的邻接顶点,如果未被访问过,则加入队列并标记为已访问
Iterator<Integer> iterator = adj[s].listIterator();
while (iterator.hasNext()) {
int n = iterator.next();
if (!visited[n]) {
visited[n] = true;
queue.add(n);
}
}
}
}
public static void main(String args[]) {
GraphBFS g = new GraphBFS(6);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(2, 5);
System.out.println("广度优先遍历结果:");
g.BFS(0);
}
}
上述示例代码中,我们首先定义了一个图的类GraphBFS,包含了图的顶点个数V和邻接表数组adj。构造函数用于初始化图的顶点和邻接表。addEdge方法用于添加边。
在BFS方法中,我们使用一个visited数组来记录顶点是否被访问过,并使用一个队列queue来保存待访问的顶点。首先将起始顶点标记为已访问,并入队。然后,开始循环遍历队列。每次从队列中取出一个顶点s,输出它,并将其未访问过的邻接顶点加入队列并标记为已访问。这样就完成了一次广度优先搜索。最终,所有顶点被访问完毕。
在main方法中,我们创建了一个图,并添加了边。然后调用BFS方法以广度优先的方式遍历图,并输出结果。
以上就是使用Java实现图的广度优先搜索的示例代码。