c语言广度优先搜索（Breadth-First Search，BFS）

广度优先搜索（Breadth-First Search，BFS）是一种用于遍历或搜索树或图的结构的算法。这个算法从图的某一结点开始遍历，然后访问所有相邻的节点。然后对这些相邻节点，再看它们的未被访问过的相邻节点，以此类推。这种方式就是广度优先，也可以理解为先访问完一层再访问下一层。

以下是一个使用广度优先搜索访问图的C语言代码示例。为了简化问题，我们假设图中的节点表示为整数，并使用邻接矩阵来表示图。代码中有详细的注释和解释。

#include <stdio.h>
#define SIZE 40

struct 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;
}

代码的主要步骤如下：

1. 创建一个队列：在广度优先搜索中，我们使用队列来存储尚未访问过的节点。在这个示例中，我们使用一个结构体来表示队列，并实现了向队列中添加元素（enqueue）、从队列中移除元素（dequeue）以及检查队列是否为空（isEmpty）的操作。

2. 创建一个图：我们使用一个结构体来表示图，并实现了创建新图（createGraph）和添加边（addEdge）的操作。在这个示例中，我们假设图是无向的，所以如果存在一条从节点A到节点B的边，那么就存在一条从节点B到节点A的边。

3. 执行广度优先搜索：

   • 首先，我们创建一个数组（visited）来记录哪些节点已经被访问过。然后，我们将起始节点添加到队列中，并标记为已访问。
   • 然后，我们进入一个while循环，直到队列为空为止。在每次循环中，我们都从队列中移除一个节点，并访问这个节点。
   • 对于每个被访问的节点，我们都遍历它的所有相邻节点，并检查它们是否已经被访问过。如果一个相邻节点尚未被访问过，那么就将它添加到队列中，并标记为已访问。

4. 主函数：在主函数中，我们创建了一个新的图，并添加了一些边。然后，我们从节点0开始执行广度优先搜索。