c语言的广度优先代码
时间: 2023-12-26 16:28:53 浏览: 28
以下是C语言实现广度优先搜索算法的代码示例:
```c
#include <stdio.h>
#define MAX_SIZE 100
// 定义队列结构
typedef struct {
int items[MAX_SIZE];
int front;
int rear;
} Queue;
// 初始化队列
void initQueue(Queue* q) {
q->front = -1;
q->rear = -1;
}
// 判断队列是否为空
int isEmpty(Queue* q) {
if (q->rear == -1)
return 1;
else
return 0;
}
// 判断队列是否已满
int isFull(Queue* q) {
if (q->rear == MAX_SIZE - 1)
return 1;
else
return 0;
}
// 入队操作
void enqueue(Queue* q, int value) {
if (isFull(q)) {
printf("队列已满,无法入队。\n");
} else {
if (q->front == -1)
q->front = 0;
q->rear++;
q->items[q->rear] = value;
}
}
// 出队操作
int dequeue(Queue* q) {
int item;
if (isEmpty(q)) {
printf("队列为空,无法出队。\n");
return -1;
} else {
item = q->items[q->front];
q->front++;
if (q->front > q->rear) {
q->front = -1;
q->rear = -1;
}
return item;
}
}
// 广度优先搜索算法
void breadthFirstSearch(int graph[][MAX_SIZE], int startVertex, int numVertices) {
int visited[MAX_SIZE] = {0}; // 记录节点是否被访问过
Queue q;
initQueue(&q);
visited[startVertex] = 1; // 标记起始节点为已访问
printf("广度优先搜索结果:\n");
printf("%d ", startVertex);
enqueue(&q, startVertex); // 将起始节点入队
while (!isEmpty(&q)) {
int currentVertex = dequeue(&q); // 出队当前节点
for (int i = 0; i < numVertices; i++) {
if (graph[currentVertex][i] == 1 && !visited[i]) {
// 如果当前节点与i节点相连且i节点未被访问过
enqueue(&q, i); // 将i节点入队
visited[i] = 1; // 标记i节点为已访问
printf("%d ", i);
}
}
}
}
int main() {
int numVertices, startVertex;
printf("请输入图的顶点数:");
scanf("%d", &numVertices);
int graph[MAX_SIZE][MAX_SIZE];
printf("请输入图的邻接矩阵:\n");
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
scanf("%d", &graph[i][j]);
}
}
printf("请输入起始顶点:");
scanf("%d", &startVertex);
breadthFirstSearch(graph, startVertex, numVertices);
return 0;
}
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)