请帮我用c语言写一个广度优先搜索的算法,以下是要求: 输入:只包含一个测试用例,第一行为一个自然数n,表示顶点的个数,第二行为n个大写字母构成的字符串,表示顶点,接下来是为一个n*n大小的矩阵,表示图的邻接关系。数字为0表示不邻接,否则为相应的边的长度。最后一行为一个字符,表示要求进行广度优先搜索的起始顶点。输出:用一行输出广度优先搜索结果,起始点为给定的顶点,各顶点之间用一个空格隔开。要求同一顶点的邻接点的访问顺序按"A"--- "Z"的字典顺序。样例输入: 5 HUEAK 00230 00074 20000 37001 04010 H 样例输出:HAEKU 输出结果要正确,这个很重要。
时间: 2024-03-24 13:36:04 浏览: 51
好的,以下是广度优先搜索的C语言实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MAX_VERTICES 26 // 最大顶点数
#define INF 1000000 // 无穷大
int graph[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
int visited[MAX_VERTICES]; // 标记是否已经访问
char vertices[MAX_VERTICES]; // 顶点名称
int queue[MAX_VERTICES]; // 存储队列
int front = -1, rear = -1; // 队列指针
// 初始化队列
void initQueue() {
front = rear = -1;
}
// 判断队列是否为空
bool isQueueEmpty() {
return front == -1 && rear == -1;
}
// 入队
void enqueue(int vertex) {
if (isQueueEmpty()) {
front++;
}
queue[++rear] = vertex;
}
// 出队
int dequeue() {
int vertex = queue[front];
if (front == rear) {
front = rear = -1;
} else {
front++;
}
return vertex;
}
// 检查当前顶点是否已访问
bool isVisited(int vertex) {
return visited[vertex] == 1;
}
// 标记当前顶点为已访问
void markVisited(int vertex) {
visited[vertex] = 1;
}
// 检查两个顶点是否邻接
bool isAdjacent(int vertex1, int vertex2) {
return graph[vertex1][vertex2] != 0;
}
// 获取与当前顶点邻接的下一个未访问的顶点
int getAdjacent(int vertex) {
for (int i = 0; i < MAX_VERTICES; i++) {
if (isAdjacent(vertex, i) && !isVisited(i)) {
return i;
}
}
return -1;
}
// 输出遍历结果
void printResult(char startVertex) {
for (int i = 0; i < MAX_VERTICES; i++) {
if (vertices[i] == startVertex) {
printf("%c", vertices[i]);
break;
}
}
for (int i = 0; i < MAX_VERTICES; i++) {
if (isVisited(i) && vertices[i] != startVertex) {
printf("%c", vertices[i]);
}
}
printf("\n");
}
// 按字典顺序排序
void sortVertices() {
for (int i = 0; i < MAX_VERTICES; i++) {
for (int j = i + 1; j < MAX_VERTICES; j++) {
if (vertices[j] < vertices[i]) {
char temp = vertices[i];
vertices[i] = vertices[j];
vertices[j] = temp;
}
}
}
}
// 广度优先搜索
void bfs(char startVertex) {
int startIndex = -1;
// 获取起始顶点的下标
for (int i = 0; i < MAX_VERTICES; i++) {
if (vertices[i] == startVertex) {
startIndex = i;
break;
}
}
// 起始顶点入队并标记为已访问
enqueue(startIndex);
markVisited(startIndex);
// 遍历邻接顶点
while (!isQueueEmpty()) {
int currVertex = dequeue();
printf("%c", vertices[currVertex]);
for (int i = getAdjacent(currVertex); i != -1; i = getAdjacent(currVertex)) {
markVisited(i);
enqueue(i);
}
}
}
int main() {
int n;
scanf("%d", &n);
// 初始化邻接矩阵
for (int i = 0; i < MAX_VERTICES; i++) {
for (int j = 0; j < MAX_VERTICES; j++) {
graph[i][j] = INF;
}
}
// 获取顶点名称
char vertexName;
for (int i = 0; i < n; i++) {
scanf(" %c", &vertexName);
vertices[i] = vertexName;
}
sortVertices(); // 排序
// 获取邻接矩阵
char edgeLength;
for (int i = 0; i < n; i++) {
getchar(); // 消耗换行符
for (int j = 0; j < n; j++) {
scanf("%c", &edgeLength);
if (edgeLength != '0') {
graph[i][j] = edgeLength - '0';
}
}
}
// 获取起始顶点并进行广度优先搜索
char startVertex;
getchar(); // 消耗换行符
scanf("%c", &startVertex);
bfs(startVertex);
return 0;
}
```
这个算法使用了邻接矩阵来存储图的结构,使用了队列来实现广度优先搜索。其中,`isVisited`、`markVisited`、`isAdjacent`、`getAdjacent` 四个函数分别用于判断当前顶点是否已访问、标记当前顶点为已访问、判断两个顶点是否邻接、获取与当前顶点邻接的下一个未访问的顶点。`printResult` 用于输出遍历结果,`sortVertices` 用于将顶点按字典顺序排序。
阅读全文