请帮我用c语言写一个广度优先搜索的算法,以下是要求: 输入只包含一个测试用例,第一行为一个自然数n,表示顶点的个数,第二行为n个大写字母构成的字符串,表示顶点,接下来是为一个n*n大小的矩阵,表示图的邻接关系。数字为0表示不邻接,否则为相应的边的长度。最后一行为一个字符,表示要求进行广度优先搜索的起始顶点。输出:用一行输出广度优先搜索结果,起始点为给定的顶点,各顶点之间用一个空格隔开。要求同一顶点的邻接点的访问顺序按“A”--- “Z”的字典顺序。 样例输入: 5 HUEAK 00230 00074 20000 37001 04010 L 样例输出:HAEKU
时间: 2024-03-24 10:35:50 浏览: 143
c/c++语言实现的广度优先搜索算法
5星 · 资源好评率100%
以下是广度优先搜索的 C 语言实现,其中用邻接矩阵表示图的结构:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX_NUM 26
// 邻接矩阵表示图的结构体
typedef struct {
char vertex[MAX_VERTEX_NUM]; // 顶点数组
int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 边数组
int vertex_num; // 顶点个数
} Graph;
// 初始化图
void init_graph(Graph *g) {
memset(g->vertex, 0, sizeof(g->vertex));
memset(g->edge, 0, sizeof(g->edge));
g->vertex_num = 0;
}
// 添加顶点
void add_vertex(Graph *g, char v) {
g->vertex[g->vertex_num++] = v;
}
// 添加边
void add_edge(Graph *g, char v1, char v2, int len) {
int i, j;
for (i = 0; i < g->vertex_num; i++) {
if (g->vertex[i] == v1) {
break;
}
}
for (j = 0; j < g->vertex_num; j++) {
if (g->vertex[j] == v2) {
break;
}
}
g->edge[i][j] = g->edge[j][i] = len;
}
// 广度优先搜索
void bfs(Graph *g, char start) {
int visited[MAX_VERTEX_NUM] = {0}; // 标记各个顶点是否被访问过
int queue[MAX_VERTEX_NUM], head = 0, tail = 0; // 定义队列
int i, j, k;
// 找到起始点
for (i = 0; i < g->vertex_num; i++) {
if (g->vertex[i] == start) {
break;
}
}
// 将起始点加入队列
visited[i] = 1;
queue[tail++] = i;
// 广度优先搜索
while (head < tail) {
k = queue[head++];
printf("%c", g->vertex[k]);
// 将与当前顶点邻接的、未被访问过的顶点按字典序加入队列
for (j = 0; j < g->vertex_num; j++) {
if (g->edge[k][j] != 0 && !visited[j]) {
visited[j] = 1;
int l, m;
char tmp;
for (l = tail; l >= head; l--) { // 从队列尾部开始查找插入位置
m = queue[l-1];
if (g->vertex[j] >= g->vertex[m]) {
break;
} else {
queue[l] = m;
}
}
queue[l] = j;
tail++;
}
}
}
}
int main() {
Graph g;
char start;
int i, j, n, len;
char v1, v2;
// 读入顶点数和顶点数组
scanf("%d", &n);
getchar();
for (i = 0; i < n; i++) {
scanf("%c", &g.vertex[i]);
getchar();
}
g.vertex_num = n;
// 读入邻接矩阵
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%1d", &len);
g.edge[i][j] = len;
}
getchar();
}
// 读入起始点
scanf("%c", &start);
// 进行广度优先搜索
bfs(&g, start);
printf("\n");
return 0;
}
```
注意,本算法中顶点数组中的顶点按照字典序排序,邻接矩阵中的 i 和 j 分别表示顶点数组中的第 i 个顶点和第 j 个顶点。在将顶点插入队列时,按字典序查找插入位置。
阅读全文