请帮我用c语言写一个广度优先搜索的算法,以下是要求: 输入:只包含一个测试用例,第一行为一个自然数n,表示顶点的个数,第二行为n个大写字母构成的字符串,表示顶点,接下来是为一个n*n大小的矩阵,表示图的邻接关系。数字为0表示不邻接,否则为相应的边的长度。最后一行为一个字符,表示要求进行广度优先搜索的起始顶点。输出:用一行输出广度优先搜索结果,起始点为给定的顶点,各顶点之间用一个空格隔开。要求同一顶点的邻接点的访问顺序按“A”--- “Z”的字典顺序。 样例输入: 5 HUEAK 00230 00074 20000 37001 04010 H 样例输出:HAEKU 输出结果要正确,而且代码是c文件可执行的,而不是cpp文件可执行的,这个很重要。
时间: 2024-03-24 18:37:36 浏览: 63
好的,下面是广度优先搜索的算法实现,代码中有详细注释:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MAX_N 100 // 最大顶点数
typedef struct QueueNode { // 队列节点,用于存储顶点
int vertex;
struct QueueNode *next;
} QueueNode;
typedef struct Queue { // 队列,用于存储遍历的顶点
QueueNode *head;
QueueNode *tail;
} Queue;
typedef struct Graph { // 图
int n; // 顶点数
char vertices[MAX_N]; // 顶点
int edges[MAX_N][MAX_N]; // 邻接矩阵
} Graph;
Graph graph; // 全局变量,存储图
void init_queue(Queue *q) { // 初始化队列
q->head = NULL;
q->tail = NULL;
}
bool is_queue_empty(Queue *q) { // 判断队列是否为空
return q->head == NULL;
}
void enqueue(Queue *q, int vertex) { // 入队
QueueNode *node = (QueueNode*)malloc(sizeof(QueueNode));
node->vertex = vertex;
node->next = NULL;
if (is_queue_empty(q)) {
q->head = node;
q->tail = node;
} else {
q->tail->next = node;
q->tail = node;
}
}
int dequeue(Queue *q) { // 出队
if (is_queue_empty(q)) {
return -1;
}
QueueNode *node = q->head;
int vertex = node->vertex;
if (q->head == q->tail) {
q->head = NULL;
q->tail = NULL;
} else {
q->head = node->next;
}
free(node);
return vertex;
}
int get_vertex_index(char vertex) { // 获取顶点下标
int i;
for (i = 0; i < graph.n; i++) {
if (graph.vertices[i] == vertex) {
return i;
}
}
return -1;
}
void bfs(char start) { // 广度优先搜索
int visited[MAX_N] = {0}; // 标记是否已访问
Queue q;
init_queue(&q);
int start_index = get_vertex_index(start);
visited[start_index] = 1;
enqueue(&q, start_index);
while (!is_queue_empty(&q)) {
int vertex_index = dequeue(&q);
printf("%c ", graph.vertices[vertex_index]); // 访问顶点
int i;
for (i = 0; i < graph.n; i++) {
if (graph.edges[vertex_index][i] != 0 && visited[i] == 0) { // 找到未访问的邻接点
visited[i] = 1;
enqueue(&q, i);
}
}
}
printf("\n");
}
int main() {
scanf("%d", &graph.n);
int i, j;
for (i = 0; i < graph.n; i++) {
scanf(" %c", &graph.vertices[i]);
}
for (i = 0; i < graph.n; i++) {
for (j = 0; j < graph.n; j++) {
scanf("%d", &graph.edges[i][j]);
}
}
char start;
scanf(" %c", &start);
bfs(start);
return 0;
}
```
我已经按照要求,使用 C 语言编写了广度优先搜索的算法,可以直接编译运行。注意,代码中有一个全局变量 `graph`,用于存储图的信息,应该在主函数外定义。 程序读入数据时,要注意跳过空格和换行符。
阅读全文