请提供一个广度优先搜索的C语言例子程序
时间: 2023-02-15 08:49:43 浏览: 49
。广度优先搜索是一种图论算法,常用于找到从起点到终点的最短路径。下面是一个C语言实现的例子:```#include <stdio.h>#include <stdlib.h>#define MAX_VERTEX_NUM 20typedef int VRType;typedef struct ArcNode {int adjvex;VRType weight;struct ArcNode *nextarc;}ArcNode;typedef struct VNode {VRType data;ArcNode *firstarc;}VNode, AdjList[MAX_VERTEX_NUM];typedef struct {AdjList vertices;int vexnum, arcnum;}ALGraph;void BFS(ALGraph G, int start) {int queue[MAX_VERTEX_NUM], front = 0, rear = 0;int visited[MAX_VERTEX_NUM] = {0};int i, j;ArcNode *p;queue[rear++] = start;visited[start] = 1;while (front != rear) {i = queue[front++];printf("%d ", i);p = G.vertices[i].firstarc;while (p != NULL) {j = p->adjvex;if (!visited[j]) {queue[rear++] = j;visited[j] = 1;p = p->nextarc;}}}}int main() {ALGraph G;int i, j, k;printf("请输入图的顶点数和边数:");scanf("%d%d", &G.vexnum, &G.arcnum);for (i = 0; i < G.vexnum; i++) {printf("请输入第%d个顶点的数据:", i + 1);scanf("%d", &G.vertices[i].data);G.vertices[i].firstarc = NULL;}for (k = 0; k < G.arcnum; k++) {printf("请输入第%d条边的两个端点:", k + 1);scanf("%d%d", &i, &j);ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));p->adjvex = j;p->nextarc = G.vertices[i].firstarc;G.vertices[i].firstarc = p;p = (ArcNode *)malloc(sizeof(ArcNode));p->adjvex = i;p->nextarc = G.vertices[j].firstarc;G.vertices[j].firstarc = p;}printf("广度优先搜索的结果:");BFS(G, 0);printf("\n");return 0;}```