帮我写一个广度优先搜索代码,使用java语言
时间: 2024-05-09 16:18:54 浏览: 77
基于BFS广度优先搜索算法代码.zip
以下是使用Java语言实现广度优先搜索的示例代码:
```java
import java.util.LinkedList;
import java.util.Queue;
public class BFS {
// 定义图的邻接矩阵
private int[][] graph;
// 定义访问状态数组
private boolean[] visited;
public BFS(int[][] graph) {
this.graph = graph;
visited = new boolean[graph.length];
}
// 广度优先搜索
public void bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(start); // 将起始节点加入队列
visited[start] = true; // 标记为已访问
while (!queue.isEmpty()) {
int curr = queue.poll(); // 取出队头元素
System.out.print(curr + " "); // 输出当前节点
// 遍历当前节点的所有邻居节点
for (int i = 0; i < graph.length; i++) {
if (graph[curr][i] == 1 && !visited[i]) { // 如果存在边且未访问
queue.offer(i); // 加入队列
visited[i] = true; // 标记为已访问
}
}
}
}
public static void main(String[] args) {
int[][] graph = {
{0, 1, 1, 0, 0},
{1, 0, 0, 1, 1},
{1, 0, 0, 1, 0},
{0, 1, 1, 0, 1},
{0, 1, 0, 1, 0}
};
BFS bfs = new BFS(graph);
bfs.bfs(0);
}
}
```
在上述代码中,我们首先定义了一个邻接矩阵来表示图,然后定义了一个访问状态数组,用于标记每个节点是否已访问。在 `bfs` 方法中,我们使用一个队列来存储待访问的节点。我们从起始节点开始,将其加入队列并标记为已访问。然后我们进入一个循环,不断从队列中取出队头元素,输出当前节点,然后遍历当前节点的所有邻居节点,如果邻居节点存在边且未被访问过,则将其加入队列并标记为已访问。最终我们可以得到广度优先搜索的遍历结果。
阅读全文