请帮我用c语言写一个广度优先搜索的算法,以下是要求: 输入:只包含一个测试用例,第一行为一个自然数n,表示顶点的个数,第二行为n个大写字母构成的字符串,表示顶点,接下来是为一个n*n大小的矩阵,表示图的邻接关系。数字为0表示不邻接,否则为相应的边的长度。最后一行为一个字符,表示要求进行广度优先搜索的起始顶点。输出:用一行输出广度优先搜索结果,起始点为给定的顶点,各顶点之间用一个空格隔开。要求同一顶点的邻接点的访问顺序按“A”--- “Z”的字典顺序。 样例输入: 5 HUEAK 00230 00074 20000 37001 04010 H 样例输出:HAEKU 输出结果要正确,而且代码是c文件可执行的,而不是cpp文件可执行的,这个很重要。
时间: 2024-03-24 07:38:33 浏览: 118
好的,以下是广度优先搜索的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MAX_N 100
typedef struct node {
int vertex; // 顶点编号
int weight; // 边的权重
struct node *next; // 指向下一个邻接点的指针
} Node;
// 邻接表中的一个顶点
typedef struct {
char name; // 顶点名称
Node *adj_list; // 指向邻接表的指针
} Vertex;
Vertex vertices[MAX_N]; // 存储所有顶点的数组
bool visited[MAX_N] = {false}; // 记录顶点是否已经被访问过
int queue[MAX_N]; // 存储待访问的顶点的队列
int front = 0, rear = 0; // 队列的头和尾
// 将顶点v1和v2之间的边加入邻接表中
void add_edge(int v1, int v2, int weight) {
Node *new_node = (Node *) malloc(sizeof(Node)); // 创建一个新的邻接点
new_node->vertex = v2;
new_node->weight = weight;
new_node->next = vertices[v1].adj_list;
vertices[v1].adj_list = new_node;
}
// 从队列中取出一个顶点进行访问
int dequeue() {
int v = queue[front];
front++;
return v;
}
// 将顶点v加入队列中
void enqueue(int v) {
queue[rear] = v;
rear++;
}
// 广度优先搜索算法
void bfs(int start) {
visited[start] = true; // 标记起始顶点为已访问
enqueue(start); // 将起始顶点加入队列中
while (front != rear) { // 队列非空时循环
int v = dequeue(); // 取出队首顶点进行访问
printf("%c ", vertices[v].name); // 输出顶点名称
// 枚举v的所有邻接点,将未访问的邻接点加入队列中
Node *p = vertices[v].adj_list;
while (p != NULL) {
int w = p->vertex;
if (!visited[w]) {
visited[w] = true;
enqueue(w);
}
p = p->next;
}
}
}
int main() {
int n; // 顶点个数
scanf("%d", &n);
// 读入顶点名称
char name[MAX_N];
scanf("%s", name);
for (int i = 0; i < n; i++) {
vertices[i].name = name[i];
vertices[i].adj_list = NULL;
}
// 读入邻接矩阵
int matrix[MAX_N][MAX_N];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &matrix[i][j]);
if (matrix[i][j] != 0) {
add_edge(i, j, matrix[i][j]);
}
}
}
// 读入起始顶点
char start;
scanf(" %c", &start);
// 找到起始顶点在数组中的下标,然后进行广度优先搜索
for (int i = 0; i < n; i++) {
if (vertices[i].name == start) {
bfs(i);
break;
}
}
return 0;
}
```
该程序使用邻接表存储图,并且使用队列实现广度优先搜索。在读入图的邻接矩阵时,如果矩阵中的元素不为0,则将该边加入邻接表中。在进行广度优先搜索时,如果一个邻接点未被访问过,则将其加入队列中。为了满足题目要求,程序还需要按字典序输出同一顶点的邻接点。
阅读全文