请帮我用c语言写一个广度优先搜索的算法,以下是要求: 输入:只包含一个测试用例,第一行为一个自然数n,表示顶点的个数,第二行为n个大写字母构成的字符串,表示顶点,接下来是为一个n*n大小的矩阵,表示图的邻接关系。数字为0表示不邻接,否则为相应的边的长度。最后一行为一个字符,表示要求进行广度优先搜索的起始顶点。输出:用一行输出广度优先搜索结果,起始点为给定的顶点,各顶点之间用一个空格隔开。要求同一顶点的邻接点的访问顺序按“A”--- “Z”的字典顺序。 样例输入: 5 HUEAK 00230 00074 20000 37001 04010 H 样例输出:HAEKU 输出结果要正确,这个很重要。还要求是c文件能运行的而非cpp文件,这也很重要
时间: 2024-03-24 15:36:45 浏览: 58
好的,以下是广度优先搜索的算法实现,代码中注释会解释每个步骤的含义和作用:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// 定义队列结构体
typedef struct {
int data[MAX_SIZE];
int front, rear;
} Queue;
// 初始化队列
void initQueue(Queue *q) {
q->front = q->rear = -1;
}
// 判断队列是否为空
int isQueueEmpty(Queue *q) {
return q->front == -1;
}
// 判断队列是否已满
int isQueueFull(Queue *q) {
return (q->rear + 1) % MAX_SIZE == q->front;
}
// 入队
void enQueue(Queue *q, int x) {
if (isQueueFull(q)) {
printf("Queue is full.\n");
exit(0);
}
if (isQueueEmpty(q)) {
q->front = q->rear = 0;
} else {
q->rear = (q->rear + 1) % MAX_SIZE;
}
q->data[q->rear] = x;
}
// 出队
int deQueue(Queue *q) {
if (isQueueEmpty(q)) {
printf("Queue is empty.\n");
exit(0);
}
int x = q->data[q->front];
if (q->front == q->rear) {
q->front = q->rear = -1;
} else {
q->front = (q->front + 1) % MAX_SIZE;
}
return x;
}
// 查找顶点在字符串中的位置
int findVertex(char vertices[], int n, char vertex) {
for (int i = 0; i < n; i++) {
if (vertices[i] == vertex) {
return i;
}
}
return -1;
}
// 广度优先搜索
void bfs(int **graph, int n, char vertices[], char startVertex) {
Queue q;
initQueue(&q);
int visited[MAX_SIZE] = {0};
int start = findVertex(vertices, n, startVertex);
visited[start] = 1;
enQueue(&q, start);
while (!isQueueEmpty(&q)) {
int v = deQueue(&q);
printf("%c ", vertices[v]);
for (int i = 0; i < n; i++) {
if (graph[v][i] && !visited[i]) {
visited[i] = 1;
enQueue(&q, i);
}
}
}
}
int main() {
int n;
char vertices[MAX_SIZE];
int **graph;
char startVertex;
scanf("%d %s", &n, vertices);
graph = (int **) malloc(n * sizeof(int *));
for (int i = 0; i < n; i++) {
graph[i] = (int *) malloc(n * sizeof(int));
for (int j = 0; j < n; j++) {
scanf("%1d", &graph[i][j]);
}
}
scanf(" %c", &startVertex);
bfs(graph, n, vertices, startVertex);
return 0;
}
```
注意,这段代码并没有进行错误处理,例如输入的数据不符合要求时程序会崩溃,但是为了简化代码,这些细节处理可以留给读者自行完成。
阅读全文