帮我用广度优先算法写一份代码,并通过实例实现它。要求建立邻接矩阵。
时间: 2024-12-13 08:25:03 浏览: 7
当然,我可以帮你理解并提供一个简单的Java代码示例,使用广度优先搜索(BFS)算法。首先,我们假设有一个邻接矩阵表示图结构,其中`adjMatrix`是一个二维数组,`graphVertices`表示图中的顶点数。
```java
import java.util.*;
class Graph {
int vertices;
boolean[][] adjMatrix;
// 构造函数
public Graph(int v) {
this.vertices = v;
adjMatrix = new boolean[v][v];
}
// 添加边的方法
void addEdge(int src, int dest) {
adjMatrix[src][dest] = true;
adjMatrix[dest][src] = true; // 图是无向的,所以添加双向边
}
// 广度优先搜索
void bfs(int start) {
boolean[] visited = new boolean[vertices]; // 记录已访问节点
// 队列用于存储待访问节点
Queue<Integer> queue = new LinkedList<>();
// 标记起点为已访问
visited[start] = true;
queue.add(start);
while (!queue.isEmpty()) {
// 取队首节点
int node = queue.poll();
System.out.print(node + " ");
// 遍历邻居节点
for (int i = 0; i < vertices; i++) {
if (adjMatrix[node][i] && !visited[i]) {
visited[i] = true;
queue.add(i);
}
}
}
}
}
public class Main {
public static void main(String[] args) {
Graph graph = new Graph(6); // 假设有6个顶点
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.addEdge(2, 3);
graph.addEdge(3, 3); // 自环
graph.addEdge(3, 4);
graph.addEdge(4, 5);
System.out.println("Breadth First Search traversal starting from vertex 2:");
graph.bfs(2);
}
}
```
这个例子中,我们创建了一个图,然后从顶点2开始执行BFS。输出将会是所有从顶点2可达的节点。运行此代码后,你会看到输出类似这样的结果:
```
Breadth First Search traversal starting from vertex 2:
2 0 1 3 4 5
```
阅读全文