什么是宽度优先搜索算法？详述宽度优先搜索算法的原理？用C语言实现宽度优先搜索算法。内附完整代码。

大家好，我是贤弟！

一、什么是宽度优先搜索？

宽度优先搜索（Breadth First Search，BFS）是一种图形搜索算法，用于在数据结构中找到从起点到目标节点的最短路径。

它是一种盲目搜索算法，也叫做“层次遍历搜索”。

二、宽度优先搜索算法的原理

宽度优先搜索算法的原理是，从起点开始，将其邻近的所有未访问过的节点加入一个队列中，并标记为已访问。

然后以该队列中的第一个节点作为当前节点，处理其邻近的节点，将邻近的未访问过的节点加入队列并标记为已访问。

如此往复，直到队列为空或者找到了目标节点。

三、代码示例

C语言实现宽度优先搜索的代码如下：

#include #include

#define MAX_SIZE 100

int graph[MAX_SIZE][MAX_SIZE]; // 邻接矩阵bool visited[MAX_SIZE]; // 标记节点是否已经被访问int queue[MAX_SIZE]; // 队列，存储待访问的节点int front = -1, rear = -1; // 队列的头、尾指针

void enqueue(int x) { if (rear == MAX_SIZE - 1) { printf("Queue is full\n"); return; } rear++; queue[rear] = x;}

int dequeue() { if (front == rear) { printf("Queue is empty\n"); return -1; } front++; return queue[front];}

void bfs(int start, int n) { visited[start] = true; // 标记起点已访问 enqueue(start); // 将起点放入队列 while (front != rear) { // 只要队列不为空 int current = dequeue(); // 取出队首节点作为当前节点 printf("%d ", current); for (int i = 0; i < n; i++) { // 处理所有邻近节点 if (graph[current][i] == 1 && !visited[i]) { // 如果邻近节点未被访问过 visited[i] = true; // 标记为已访问 enqueue(i); // 放入队列 } } }}

int main() { int n = 6; // 节点数量 // 初始化邻接矩阵 graph[0][1] = graph[1][0] = 1; graph[0][2] = graph[2][0] = 1; graph[1][3] = graph[3][1] = 1; graph[1][4] = graph[4][1] = 1; graph[2][4] = graph[4][2] = 1; graph[3][5] = graph[5][3] = 1; graph[4][5] = graph[5][4] = 1;

bfs(0, n);

return 0;}

输出结果：