c语言广度优先搜索（Breadth-First Search，BFS）
广度优先搜索（Breadth-First Search，BFS）是一种用于遍历或搜索树或图的结构的算法。这个算法从图的某一结点开始遍历，然后访问所有相邻的节点。然后对这些相邻节点，再看它们的未被访问过的相邻节点，以此类推。这种方式就是广度优先，也可以理解为先访问完一层再访问下一层。
以下是一个使用广度优先搜索访问图的C语言代码示例。为了简化问题，我们假设图中的节点表示为整数，并使用邻接矩阵来表示图。代码中有详细的注释和解释。
#include <stdio.h>
#define SIZE 40struct queue {int items[SIZE];int front;int rear;
};// 创建一个新的队列
struct queue* createQueue() {struct queue* q = malloc(sizeof(struct queue));q->front = -1;q->rear = -1;return q;
}// 向队列中添加元素
void enqueue(struct queue* q, int value) {if (q->rear == SIZE - 1)printf("\nQueue is Full!!");else {if (q->front == -1)q->front = 0;q->rear++;q->items[q->rear] = value;}
}// 从队列中移除元素
int dequeue(struct queue* q) {int item;if (q->front == -1) {printf("Queue is empty");item = -1;} else {item = q->items[q->front];q->front++;if (q->front > q->rear) {q->front = q->rear = -1;}}return item;
}// 检查队列是否为空
int isEmpty(struct queue* q) {if (q->rear == -1) return 1;else return 0;
}// 创建一个图
struct Graph {int numVertices;int** adjMatrix;
};// 创建一个新的图
struct Graph* createGraph(int vertices) {struct Graph* graph = malloc(sizeof(struct Graph));graph->numVertices = vertices;graph->adjMatrix = malloc(vertices * sizeof(int*));for (int i = 0; i < vertices; i++) {graph->adjMatrix[i] = malloc(vertices * sizeof(int));}// 初始化邻接矩阵for (int i = 0; i < vertices; i++) {for (int j = 0; j < vertices; j++)graph->adjMatrix[i][j] = 0;}return graph;
}// 添加边
void addEdge(struct Graph* graph, int src, int dest) {graph->adjMatrix[src][dest] = 1;graph->adjMatrix[dest][src] = 1;
}// 执行广度优先搜索
void bfs(struct Graph* graph, int startVertex) {struct queue* q = createQueue();int visited[graph->numVertices];for (int i = 0; i < graph->numVertices; i++)visited[i] = 0;visited[startVertex] = 1;enqueue(q, startVertex);while (!isEmpty(q)) {printQueue(q);int currentVertex = dequeue(q);printf("Visited %d\n", currentVertex);// 遍历当前节点的所有邻居for (int i = 0; i < graph->numVertices; i++) {if (graph->adjMatrix[currentVertex][i] == 1 && !visited[i]) {enqueue(q, i);visited[i] = 1;}}}
}// 主函数
int main() {struct Graph* graph = createGraph(6);addEdge(graph, 0, 1);addEdge(graph, 0, 2);addEdge(graph, 1, 2);addEdge(graph, 1, 4);addEdge(graph, 1, 3);addEdge(graph, 2, 4);addEdge(graph, 3, 4);bfs(graph, 0);return 0;
}
代码的主要步骤如下：
-
创建一个队列：在广度优先搜索中，我们使用队列来存储尚未访问过的节点。在这个示例中，我们使用一个结构体来表示队列，并实现了向队列中添加元素（enqueue）、从队列中移除元素（dequeue）以及检查队列是否为空（isEmpty）的操作。
-
创建一个图：我们使用一个结构体来表示图，并实现了创建新图（createGraph）和添加边（addEdge）的操作。在这个示例中，我们假设图是无向的，所以如果存在一条从节点A到节点B的边，那么就存在一条从节点B到节点A的边。
-
执行广度优先搜索：
- 首先，我们创建一个数组（visited）来记录哪些节点已经被访问过。然后，我们将起始节点添加到队列中，并标记为已访问。
- 然后，我们进入一个while循环，直到队列为空为止。在每次循环中，我们都从队列中移除一个节点，并访问这个节点。
- 对于每个被访问的节点，我们都遍历它的所有相邻节点，并检查它们是否已经被访问过。如果一个相邻节点尚未被访问过，那么就将它添加到队列中，并标记为已访问。
-
主函数：在主函数中，我们创建了一个新的图，并添加了一些边。然后，我们从节点0开始执行广度优先搜索。