java实现广度优先遍历无向图邻接表
时间: 2023-12-27 17:25:38 浏览: 96
java使用邻接表对图进行深度和广度优先遍历
以下是Java实现广度优先遍历无向图邻接表的示例代码:
```java
import java.util.LinkedList;
import java.util.Queue;
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);
adj[w].add(v);
}
// 广度优先遍历
void BFS(int s) {
boolean[] visited = new boolean[V]; // 记录顶点是否被访问过
Queue<Integer> queue = new LinkedList<>(); // 创建一个队列用于BFS
visited[s] = true; // 标记起始顶点为已访问
queue.add(s); // 将起始顶点加入队列
while (!queue.isEmpty()) {
s = queue.poll(); // 出队并打印
System.out.print(s + " ");
// 遍历与当前顶点相邻的顶点
for (int n : adj[s]) {
if (!visited[n]) {
visited[n] = true; // 标记相邻顶点为已访问
queue.add(n); // 将相邻顶点加入队列
}
}
}
}
}
public class Main {
public static void main(String[] args) {
Graph g = new Graph(5); // 创建一个有5个顶点的图
// 添加边
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
System.out.println("广度优先遍历结果:");
g.BFS(0); // 从顶点0开始进行广度优先遍历
}
}
```
阅读全文