请用C语言编写函数对用邻接矩阵表示的有向图进行广度优先遍历
时间: 2024-01-03 11:04:43 浏览: 40
以下是对用邻接矩阵表示的有向图进行广度优先遍历的C语言函数实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef struct {
int vertex[MAX_VERTEX_NUM]; // 存放顶点信息
int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存放边信息,0表示无边,1表示有边
int vertex_num; // 顶点数
int arc_num; // 边数
} Graph;
// 初始化图
void init_graph(Graph *g) {
int i, j;
printf("请输入图的顶点数和边数(用空格隔开):");
scanf("%d %d", &(g->vertex_num), &(g->arc_num));
printf("请输入图的顶点信息:");
for (i = 0; i < g->vertex_num; i++) {
scanf("%d", &(g->vertex[i]));
}
for (i = 0; i < g->vertex_num; i++) {
for (j = 0; j < g->vertex_num; j++) {
g->arc[i][j] = 0;
}
}
printf("请输入图的边信息(用空格隔开):\n");
for (i = 0; i < g->arc_num; i++) {
int start, end;
scanf("%d %d", &start, &end);
g->arc[start][end] = 1;
}
}
// 广度优先遍历
void bfs(Graph *g, int start) {
int visited[MAX_VERTEX_NUM] = {0}; // 记录每个顶点是否被访问过
int queue[MAX_VERTEX_NUM]; // 队列
int front = -1, rear = -1; // 队列的头尾指针
int i, v;
visited[start] = 1; // 标记起始顶点为已访问
printf("%d ", g->vertex[start]); // 访问起始顶点
queue[++rear] = start; // 将起始顶点入队
while (front != rear) { // 当队列不为空时
v = queue[++front]; // 取出队列头顶点
for (i = 0; i < g->vertex_num; i++) { // 遍历该顶点的所有邻接顶点
if (g->arc[v][i] == 1 && !visited[i]) { // 如果该顶点与当前顶点有边且未被访问过
visited[i] = 1; // 标记该顶点为已访问
printf("%d ", g->vertex[i]); // 访问该顶点
queue[++rear] = i; // 将该顶点入队
}
}
}
}
int main() {
Graph g;
init_graph(&g);
printf("广度优先遍历的结果为:");
bfs(&g, 0); // 从顶点0开始进行广度优先遍历
printf("\n");
return 0;
}
```
其中,`Graph`结构体表示图,包括顶点信息、边信息、顶点数和边数等。`init_graph`函数用于初始化图,包括输入顶点信息、边信息等。`bfs`函数实现广度优先遍历,其中使用队列来存储待访问的顶点。在遍历过程中,每次取出队列头顶点,并访问它的所有邻接顶点,将未访问过的邻接顶点入队。最后,`main`函数中调用`init_graph`函数初始化图,并从顶点0开始进行广度优先遍历,输出遍历结果。