java bfs打印路径
时间: 2023-11-12 14:58:09 浏览: 51
好的,关于 Java 实现 BFS 并打印路径,可以参考以下代码:
```java
import java.util.*;
public class BFS {
static int[][] graph = new int[][]{
{0, 1, 1, 0, 0},
{1, 0, 1, 1, 0},
{1, 1, 0, 1, 1},
{0, 1, 1, 0, 1},
{0, 0, 1, 1, 0}
};
static int[] visited = new int[graph.length];
static int[] pre = new int[graph.length];
public static void bfs(int start, int end) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
visited[start] = 1;
while (!queue.isEmpty()) {
int cur = queue.poll();
for (int i = 0; i < graph[cur].length; i++) {
if (graph[cur][i] == 1 && visited[i] == 0) {
queue.offer(i);
visited[i] = 1;
pre[i] = cur;
if (i == end) {
printPath(start, end);
return;
}
}
}
}
}
public static void printPath(int start, int end) {
Stack<Integer> stack = new Stack<>();
int cur = end;
while (cur != start) {
stack.push(cur);
cur = pre[cur];
}
stack.push(start);
while (!stack.isEmpty()) {
System.out.print(stack.pop() + " ");
}
}
public static void main(String[] args) {
bfs(0, 4);
}
}
```
这里的 `graph` 是一个邻接矩阵,表示图的结构。`visited` 数组用于记录每个节点是否被访问过,`pre` 数组用于记录每个节点的前驱节点。在 BFS 的过程中,如果找到了终点,则调用 `printPath` 方法打印路径。