void BFS(int start) { int queue[MAX]; int front = 0; int rear = 0; queue[rear++] = start; visited[start] = 1; while (front < rear) { int cur = queue[front++]; printf("%d ", cur); for (int i = 0; i < n; i++) { if (Graph[cur][i] && !visited[i]) { queue[rear++] = i; visited[i] = 1; } } } }

这是BFS函数的具体实现。参数start表示起始顶点，queue是队列，visited是标记数组，用来记录每个顶点是否已经被访问过。MAX表示队列的最大长度，可以根据需要进行调整。

该函数首先将起始顶点入队，并将其标记为已访问。然后进入while循环，只要队列不为空就一直循环，每次取出队首元素，并输出该元素。然后遍历该元素的所有邻接点，如果该邻接点没有被访问过，则将其入队并标记为已访问。

需要注意的是，该代码中没有对队列是否已满进行判断，如果队列已满，则可能会导致程序崩溃。另外，该代码中没有对图是否连通进行判断，如果图不连通，则需要对所有未访问的顶点进行遍历。

相关问题

#include <stdio.h> #include <stdlib.h> #define MAX_VERTICES 50 typedef struct Graph { int num_vertices; int adj_matrix[MAX_VERTICES][MAX_VERTICES]; } Graph; void dfs(Graph *graph, int vertex, int visited[]) { visited[vertex] = 1; printf("%d ", vertex); for (int i = 0; i < graph->num_vertices; i++) { if (graph->adj_matrix[vertex][i] == 1 && visited[i] == 0) { dfs(graph, i, visited); } } } void bfs(Graph *graph, int vertex, int visited[]) { int queue[MAX_VERTICES]; int front = -1; int rear = -1; visited[vertex] = 1; queue[++rear] = vertex; while (front != rear) { vertex = queue[++front]; printf("%d ", vertex); for (int i = 0; i < graph->num_vertices; i++) { if (graph->adj_matrix[vertex][i] == 1 && visited[i] == 0) { visited[i] = 1; queue[++rear] = i; } } } } int main() { Graph *graph = (Graph*) malloc(sizeof(Graph)); graph->num_vertices = 6; int adj_matrix[6][6] = { {0, 1, 1, 0, 0, 0}, {1, 0, 0, 1, 1, 0}, {1, 0, 0, 0, 0, 1}, {0, 1, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 1}, {0, 0, 1, 0, 1, 0} }; for (int i = 0; i < graph->num_vertices; i++) { for (int j = 0; j < graph->num_vertices; j++) { graph->adj_matrix[i][j] = adj_matrix[i][j]; } } int visited[MAX_VERTICES] = {0}; printf("DFS: "); dfs(graph, 0, visited); printf("\n"); for (int i = 0; i < graph->num_vertices; i++) { visited[i] = 0; } printf("BFS: "); bfs(graph, 0, visited); printf("\n"); free(graph); return 0; }解释这些代码

这段代码是一个基于邻接矩阵表示法的图的深度优先遍历（DFS）和广度优先遍历（BFS）算法的实现。具体解释如下：

首先，定义了一个Graph结构体，其中包含了图的顶点数和邻接矩阵adj_matrix，用于存储图的边信息。

然后，定义了dfs和bfs两个函数。其中dfs函数用于深度优先遍历图，它采用递归的方式遍历图中的每个连通分量（connected component），并将遍历过的节点打印出来。bfs函数则用于广度优先遍历图，它采用队列的方式遍历图中的每个连通分量，也将遍历过的节点打印出来。

在main函数中，先使用malloc函数动态分配了一个Graph结构体，并初始化了图的顶点数和邻接矩阵。然后，定义了一个visited数组，用于记录每个节点是否被访问过。接着，分别调用了dfs和bfs函数，传入图、起始节点和visited数组，进行遍历，并打印出遍历结果。最后，使用free函数释放了Graph结构体的内存。

总体来说，这段代码是一个简单而实用的图的遍历算法实现，可以用于求解图的连通性、最短路径等问题。

#include <stdio.h> #include <stdlib.h> #define MAXN 50 int visited[MAXN]; // 记录节点是否被访问过 int queue[MAXN]; // 队列 int front=0,rear=0; // 队首和队尾指针 int n; // 图的节点个数 // 遍历节点v void BFS(int v, int G[][MAXN]) { visited[v]=1; // 标记为已访问 queue[rear++]=v; // 加入队列 while(front<rear) { // 队列非空 int u=queue[front++]; // 取出队首节点 printf("%d ",u); // 输出节点编号 for(int i=0;i<n;i++) { if (G[u][i]&&!visited[i]) { // 若节点i与u相邻且未访问 visited[i] = 1; // 标记为已访问 queue[rear++] = i; // 加入队列 } } } } int main() { int i,j; int G[MAXN][MAXN]; // 图的邻接矩阵 scanf("%d",&n); for(i=0;i<n;i++) { for(j=0;j<n;j++) { scanf("%d",&G[i][j]); } } for(i=0;i<n;i++) { if (!visited[i]) { // 若节点i未被访问 BFS(i,G); // 从节点i开始遍历 } } printf("\n"); return 0; }

这段代码实现了一个图的广度优先遍历算法，使用了邻接矩阵来表示图。其中visited数组用于记录节点是否被访问过，queue数组用于实现队列，front和rear分别是队首和队尾指针。输入时先读入节点个数n，然后再读入邻接矩阵G。接下来对于每个未被访问过的节点i，都从它开始进行广度优先遍历，并输出遍历结果。