java的bfs代码示例
时间: 2024-01-29 08:10:17 浏览: 29
以下是一个Java的BFS代码示例:
```java
import java.util.LinkedList;
import java.util.Queue;
class Node {
int x;
int y;
}
public class BFSExample {
public static void main(String[] args) {
Queue<Node> q = new LinkedList<>();
Node node = new Node();
node.x = 1;
node.y = 2;
q.offer(node);
node = new Node(); // 创建新的结点
node.x = 3;
node.y = 3;
q.offer(node);
for (Node qq : q) {
System.out.println(qq.x + "," + qq.y + " ");
}
}
}
```
相关问题
贪吃蛇bfs算法java代码
贪吃蛇游戏是一个经典的游戏,BFS算法可以用来实现贪吃蛇的自动寻路功能。下面是一个简单的贪吃蛇BFS算法的Java代码示例:
```java
import java.util.*;
class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public class SnakeGame {
private int[][] grid;
private int width;
private int height;
private int[] dx = {-1, 0, 1, 0}; // 上、右、下、左
private int[] dy = {0, 1, 0, -1};
public SnakeGame(int width, int height) {
this.width = width;
this.height = height;
this.grid = new int[width][height];
}
public int bfs(Point start, Point target) {
Queue<Point> queue = new LinkedList<>();
boolean[][] visited = new boolean[width][height];
queue.offer(start);
visited[start.x][start.y] = true;
int steps = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
Point curr = queue.poll();
if (curr.x == target.x && curr.y == target.y) {
return steps;
}
for (int j = 0; j < 4; j++) {
int newX = curr.x + dx[j];
int newY = curr.y + dy[j];
if (newX >= 0 && newX < width && newY >= 0 && newY < height && !visited[newX][newY]) {
queue.offer(new Point(newX, newY));
visited[newX][newY] = true;
}
}
}
steps++;
}
return -1; // 如果无法到达目标点,返回-1
}
public static void main(String[] args) {
int width = 10;
int height = 10;
SnakeGame game = new SnakeGame(width, height);
Point start = new Point(0, 0);
Point target = new Point(9, 9);
int steps = game.bfs(start, target);
if (steps == -1) {
System.out.println("无法到达目标点");
} else {
System.out.println("到达目标点的最短步数为:" + steps);
}
}
}
```
这段代码实现了一个简单的贪吃蛇游戏,并使用BFS算法寻找从起点到目标点的最短路径。在代码中,`bfs`方法使用队列来进行广度优先搜索,`visited`数组用于记录已经访问过的点,`steps`变量用于记录步数。最后,在`main`方法中创建了一个SnakeGame对象,并调用`bfs`方法来计算最短步数。
java bfs创建二叉树
要使用广度优先搜索(BFS)算法创建二叉树,你可以按层级顺序遍历给定的节点数据,并为每个数据创建一个二叉树节点。
下面是一个使用Java语言实现BFS创建二叉树的示例代码:
```java
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public class BinaryTree {
public static void main(String[] args) {
int[] data = {1, 2, 3, 4, 5, 6, 7};
TreeNode root = createBinaryTree(data);
System.out.println("BFS traversal:");
bfsTraversal(root);
}
public static TreeNode createBinaryTree(int[] data) {
if (data == null || data.length == 0) {
return null;
}
TreeNode root = new TreeNode(data[0]);
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int i = 1;
while (!queue.isEmpty() && i < data.length) {
TreeNode currNode = queue.poll();
// 创建左子节点
if (i < data.length) {
currNode.left = new TreeNode(data[i]);
queue.offer(currNode.left);
i++;
}
// 创建右子节点
if (i < data.length) {
currNode.right = new TreeNode(data[i]);
queue.offer(currNode.right);
i++;
}
}
return root;
}
public static void bfsTraversal(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode currNode = queue.poll();
System.out.print(currNode.val + " ");
if (currNode.left != null) {
queue.offer(currNode.left);
}
if (currNode.right != null) {
queue.offer(currNode.right);
}
}
}
}
```
在上面的示例代码中,我们首先定义了一个`TreeNode`类来表示二叉树节点。然后,在`createBinaryTree`方法中,我们使用一个队列(`Queue`)来辅助BFS算法的实现。我们按层级顺序遍历给定的节点数据,并为每个数据创建一个二叉树节点,并将其加入到队列中。在`bfsTraversal`方法中,我们使用另一个队列来进行广度优先遍历,输出每个节点的值。
以上就是使用BFS算法创建二叉树的Java示例代码。希望能对你有所帮助!如果还有其他问题,请随时提问。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)