BFS邻接矩阵C语言

BFS（宽度优先搜索）是一种用于遍历或搜索图（特别是无权图或加权非负图）的数据结构算法，它从源节点开始，逐层扩展节点，直到找到目标节点或者遍历完整个图。在使用邻接矩阵表示图时，C语言中实现BFS的基本步骤如下：

1. **邻接矩阵**: 邻接矩阵是一个二维数组，其中行代表起点，列代表终点。如果两个顶点之间有边相连，对应的矩阵元素值为1（通常二进制表示），否则为0。

2. **初始化**:
- 初始化一个队列，将起始节点入队。
- 创建一个布尔数组标记已访问过的节点，初始时所有节点标记为未访问。

3. **循环**:
- 取出队首节点。
- 对于该节点的每一个相邻节点，如果它们没有被访问过，标记为已访问，然后入队。
- 更新队列和标记数组。

4. **递归调用**:
- 如果找到目标节点，返回成功；若队列为空仍没有找到目标，返回失败。

5. **代码实现**:

   #include <stdio.h>
   #include <stdbool.h>
   #define ROWS 5
   #define COLS 5

   bool visited[ROWS][COLS];
   bool found;

   void bfs(int src, int graph[][COLS], int V) {
       int i, j;
       int queue[ROWS * COLS], front = 0, rear = 0;

       visited[src][src] = true;
       queue[rear++] = src;

       while (front != rear) {
           src = queue[front++];
           printf("(%d)", src);

           for (i = 0; i < V; i++) {
               if (graph[src][i] && !visited[i][src]) {
                   visited[i][src] = true;
                   queue[rear++] = i;
                   if (i == target) {  // 找到目标节点
                       found = true;
                       break;
                   }
               }
           }
       }
       if (!found)
           printf("的目标节点未找到");
   }

   // 使用函数的地方
   int main() {
       int graph[ROWS][COLS] = {/* 图的邻接矩阵 */};
       int V = ROWS;  // 图中的节点数
       int start = 0, target = 4;  // 起始和目标节点
       bfs(start, graph, V);
       return 0;
   }