Java实现BFS算法
时间: 2023-10-02 15:07:57 浏览: 71
下面是Java实现BFS算法的示例代码:
```
import java.util.*;
public class BFS {
// 定义图的邻接矩阵表示
private int[][] graph;
// 定义存储节点是否被访问的数组
private boolean[] visited;
// 定义存储遍历结果的队列
private Queue<Integer> result;
public BFS(int[][] graph) {
this.graph = graph;
visited = new boolean[graph.length];
result = new LinkedList<>();
}
// BFS算法的实现
public void bfsTraversal(int startNode) {
Queue<Integer> queue = new LinkedList<>();
visited[startNode] = true;
queue.offer(startNode);
while (!queue.isEmpty()) {
int node = queue.poll();
result.offer(node);
for (int i = 0; i < graph[node].length; i++) {
if (graph[node][i] == 1 && !visited[i]) {
visited[i] = true;
queue.offer(i);
}
}
}
}
// 获取遍历结果
public Queue<Integer> getResult() {
return result;
}
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 bfs = new BFS(graph);
bfs.bfsTraversal(0);
// 输出遍历结果
Queue<Integer> result = bfs.getResult();
while (!result.isEmpty()) {
System.out.print(result.poll() + " ");
}
}
}
```
该代码实现了BFS算法,并对一个示例图进行了遍历。其中,`graph`数组表示示例图的邻接矩阵,`visited`数组表示节点是否被访问,`result`队列用于存储遍历结果。`bfsTraversal`方法实现了BFS算法,`getResult`方法用于获取遍历结果。在`main`方法中创建BFS对象并进行遍历,最后输出遍历结果。