与深度优先搜索不同，BFS 从起始顶点开始，沿着图的宽度遍历图的节点，直到找到目标节点或遍历完整个图。BFS 通常使用队列来实现，它遵循以下步骤：
1. 将起始顶点放入队列中，并标记为已访问。
2. 从队列中取出一个顶点作为当前顶点。
3. 对于当前顶点的每个未访问的邻居顶点，将其标记为已访问并放入队列中。
4. 重复步骤 2 和步骤 3，直到队列为空。
BFS 的特点包括：
- 广度优先：按照层级顺序逐层遍历图的节点，先访问离起始顶点最近的节点。
- 最短路径：如果图中的边具有相同的权重，则从起始顶点到任意顶点的路径都是最短路径。
- 非递归性质：BFS 使用队列来存储待访问的节点，因此是一个非递归的算法。
BFS 在许多领域都有广泛的应用，包括图论、网络路由算法、最短路径算法等。
以下是 C、C++、Java、Python 四种语言下实现广度优先搜索的示例代码：
### C 语言
```c #include <stdio.h> #include <stdlib.h> #define MAX_VERTICES 100 typedef struct { int data[MAX_VERTICES]; int front, rear; } Queue; void init(Queue *q) { q->front = 0; q->rear = -1; } void enqueue(Queue *q, int value) { q->data[++(q->rear)] = value; } int dequeue(Queue *q) { return q->data[(q->front)++]; } int isEmpty(Queue *q) { return q->front > q->rear; } typedef struct { int vertices[MAX_VERTICES][MAX_VERTICES]; int visited[MAX_VERTICES]; int num_vertices; } Graph; void initGraph(Graph *g, int num_vertices) { g->num_vertices = num_vertices; for (int i = 0; i < num_vertices; i++) { g->visited[i] = 0; for (int j = 0; j < num_vertices; j++) { g->vertices[i][j] = 0; } } } void addEdge(Graph *g, int v1, int v2) { g->vertices[v1][v2] = 1; g->vertices[v2][v1] = 1; } void bfs(Graph *g, int start) { Queue q; init(&q); enqueue(&q, start); g->visited[start] = 1; while (!isEmpty(&q)) { int current = dequeue(&q); printf("%d ", current); for (int i = 0; i < g->num_vertices; i++) { if (g->vertices[current][i] == 1 && g->visited[i] == 0) { enqueue(&q, i); g->visited[i] = 1; } } } } int main() { Graph g; initGraph(&g, 6); addEdge(&g, 0, 1); addEdge(&g, 0, 2); addEdge(&g, 1, 3); addEdge(&g, 1, 4); addEdge(&g, 2, 5); printf("BFS traversal starting from vertex 0: "); bfs(&g, 0); return 0; } ```
### C++ 语言
```cpp #include <iostream> #include <vector> #include <queue> using namespace std; void bfs(vector<vector<int>>& graph, vector<bool>& visited, int start) { queue<int> q; q.push(start); visited[start] = true; while (!q.empty()) { int current = q.front(); q.pop(); cout << current << " "; for (int i = 0; i < graph[current].size(); i++) { int neighbor = graph[current][i]; if (!visited[neighbor]) { q.push(neighbor); visited[neighbor] = true; } } } } int main() { vector<vector<int>> graph = {{1, 2}, {0, 3, 4}, {0, 5}, {1}, {1}, {2}}; vector<bool> visited(graph.size(), false); cout << "BFS traversal starting from vertex 0: "; bfs(graph, visited, 0); return 0; } ```
### Java 语言
```java import java.util.LinkedList; import java.util.Queue; class Graph { private int numVertices; private int[][] vertices; private boolean[] visited; public Graph(int numVertices) { this.numVertices = numVertices; vertices = new int[numVertices][numVertices]; visited = new boolean[numVertices]; } public void addEdge(int v1, int v2) { vertices[v1][v2] = 1; vertices[v2][v1] = 1; } public void bfs(int start) { Queue<Integer> queue = new LinkedList<>(); queue.add(start); visited[start] = true; while (!queue.isEmpty()) { int current = queue.poll(); System.out.print(current + " "); for (int i = 0; i < numVertices; i++) { if (vertices[current][i] == 1 && !visited[i]) { queue.add(i); visited[i] = true; } } } } public static void main(String[] args) { Graph graph = new Graph(6); graph.addEdge(0, 1
```java import java.util.LinkedList; import java.util.Queue; class Graph { private int numVertices; private int[][] vertices; private boolean[] visited; public Graph(int numVertices) { this.numVertices = numVertices; vertices = new int[numVertices][numVertices]; visited = new boolean[numVertices]; } public void addEdge(int v1, int v2) { vertices[v1][v2] = 1; vertices[v2][v1] = 1; } public void bfs(int start) { Queue<Integer> queue = new LinkedList<>(); queue.add(start); visited[start] = true; while (!queue.isEmpty()) { int current = queue.poll(); System.out.print(current + " "); for (int i = 0; i < numVertices; i++) { if (vertices[current][i] == 1 && !visited[i]) { queue.add(i); visited[i] = true; } } } } public static void main(String[] args) { Graph graph = new Graph(6); graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(1, 3); graph.addEdge(1, 4); graph.addEdge(2, 5); System.out.print("从顶点 0 开始的广度优先遍历："); graph.bfs(0); } } ```
这段代码创建了一个包含 6 个顶点的图，并在它们之间添加了边。然后，它从顶点 0 开始执行广度优先遍历，并打印遍历顺序。
