给出bfs的Java代码实现
时间: 2024-04-09 14:28:58 浏览: 48
当然可以!以下是一个基本的BFS(广度优先搜索)的Java代码实现:
```java
import java.util.*;
class Graph {
private int V; // 图的顶点数
private LinkedList<Integer> adj[]; // 邻接表表示图
// 构造函数
Graph(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);
}
// BFS遍历
void BFS(int s) {
// 标记所有顶点为未访问
boolean visited[] = new boolean[V];
// 创建一个队列用于BFS
LinkedList<Integer> queue = new LinkedList<>();
// 标记当前节点为已访问并将其入队列
visited[s] = true;
queue.add(s);
while (queue.size() != 0) {
// 出队列并打印
s = queue.poll();
System.out.print(s + " ");
// 获取相邻的未访问节点并标记为已访问,然后入队列
Iterator<Integer> i = adj[s].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n]) {
visited[n] = true;
queue.add(n);
}
}
}
}
public static void main(String args[]) {
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
System.out.println("BFS 遍历结果:");
g.BFS(2);
}
}
```
这段代码实现了一个无向图的BFS遍历。在`main`方法中,我们创建了一个图,并添加了一些边。然后,我们调用`BFS`方法来进行广度优先搜索,并打印遍历结果。
希望这个代码能够帮到你!如果有任何疑问,请随时提问。
阅读全文