c语言广度优先搜索(Breadth-First Search,BFS)

2023-12-27 16:12

本文主要是介绍c语言广度优先搜索(Breadth-First Search,BFS),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

广度优先搜索(Breadth-First Search,BFS)是一种用于遍历或搜索树或图的结构的算法。这个算法从图的某一结点开始遍历,然后访问所有相邻的节点。然后对这些相邻节点,再看它们的未被访问过的相邻节点,以此类推。这种方式就是广度优先,也可以理解为先访问完一层再访问下一层。

以下是一个使用广度优先搜索访问图的C语言代码示例。为了简化问题,我们假设图中的节点表示为整数,并使用邻接矩阵来表示图。代码中有详细的注释和解释。

#include <stdio.h>
#define SIZE 40struct queue {int items[SIZE];int front;int rear;
};// 创建一个新的队列
struct queue* createQueue() {struct queue* q = malloc(sizeof(struct queue));q->front = -1;q->rear = -1;return q;
}// 向队列中添加元素
void enqueue(struct queue* q, int value) {if (q->rear == SIZE - 1)printf("\nQueue is Full!!");else {if (q->front == -1)q->front = 0;q->rear++;q->items[q->rear] = value;}
}// 从队列中移除元素
int dequeue(struct queue* q) {int item;if (q->front == -1) {printf("Queue is empty");item = -1;} else {item = q->items[q->front];q->front++;if (q->front > q->rear) {q->front = q->rear = -1;}}return item;
}// 检查队列是否为空
int isEmpty(struct queue* q) {if (q->rear == -1) return 1;else return 0;
}// 创建一个图
struct Graph {int numVertices;int** adjMatrix;
};// 创建一个新的图
struct Graph* createGraph(int vertices) {struct Graph* graph = malloc(sizeof(struct Graph));graph->numVertices = vertices;graph->adjMatrix = malloc(vertices * sizeof(int*));for (int i = 0; i < vertices; i++) {graph->adjMatrix[i] = malloc(vertices * sizeof(int));}// 初始化邻接矩阵for (int i = 0; i < vertices; i++) {for (int j = 0; j < vertices; j++)graph->adjMatrix[i][j] = 0;}return graph;
}// 添加边
void addEdge(struct Graph* graph, int src, int dest) {graph->adjMatrix[src][dest] = 1;graph->adjMatrix[dest][src] = 1;
}// 执行广度优先搜索
void bfs(struct Graph* graph, int startVertex) {struct queue* q = createQueue();int visited[graph->numVertices];for (int i = 0; i < graph->numVertices; i++)visited[i] = 0;visited[startVertex] = 1;enqueue(q, startVertex);while (!isEmpty(q)) {printQueue(q);int currentVertex = dequeue(q);printf("Visited %d\n", currentVertex);// 遍历当前节点的所有邻居for (int i = 0; i < graph->numVertices; i++) {if (graph->adjMatrix[currentVertex][i] == 1 && !visited[i]) {enqueue(q, i);visited[i] = 1;}}}
}// 主函数
int main() {struct Graph* graph = createGraph(6);addEdge(graph, 0, 1);addEdge(graph, 0, 2);addEdge(graph, 1, 2);addEdge(graph, 1, 4);addEdge(graph, 1, 3);addEdge(graph, 2, 4);addEdge(graph, 3, 4);bfs(graph, 0);return 0;
}

代码的主要步骤如下:

  1. 创建一个队列:在广度优先搜索中,我们使用队列来存储尚未访问过的节点。在这个示例中,我们使用一个结构体来表示队列,并实现了向队列中添加元素(enqueue)、从队列中移除元素(dequeue)以及检查队列是否为空(isEmpty)的操作。

  2. 创建一个图:我们使用一个结构体来表示图,并实现了创建新图(createGraph)和添加边(addEdge)的操作。在这个示例中,我们假设图是无向的,所以如果存在一条从节点A到节点B的边,那么就存在一条从节点B到节点A的边。

  3. 执行广度优先搜索

    • 首先,我们创建一个数组(visited)来记录哪些节点已经被访问过。然后,我们将起始节点添加到队列中,并标记为已访问。
    • 然后,我们进入一个while循环,直到队列为空为止。在每次循环中,我们都从队列中移除一个节点,并访问这个节点。
    • 对于每个被访问的节点,我们都遍历它的所有相邻节点,并检查它们是否已经被访问过。如果一个相邻节点尚未被访问过,那么就将它添加到队列中,并标记为已访问。
  4. 主函数:在主函数中,我们创建了一个新的图,并添加了一些边。然后,我们从节点0开始执行广度优先搜索。

这篇关于c语言广度优先搜索(Breadth-First Search,BFS)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/543696

相关文章

C语言中的数据类型强制转换

《C语言中的数据类型强制转换》:本文主要介绍C语言中的数据类型强制转换方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C语言数据类型强制转换自动转换强制转换类型总结C语言数据类型强制转换强制类型转换:是通过类型转换运算来实现的,主要的数据类型转换分为自动转换

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

C语言实现两个变量值交换的三种方式

《C语言实现两个变量值交换的三种方式》两个变量值的交换是编程中最常见的问题之一,以下将介绍三种变量的交换方式,其中第一种方式是最常用也是最实用的,后两种方式一般只在特殊限制下使用,需要的朋友可以参考下... 目录1.使用临时变量(推荐)2.相加和相减的方式(值较大时可能丢失数据)3.按位异或运算1.使用临时

使用C语言实现交换整数的奇数位和偶数位

《使用C语言实现交换整数的奇数位和偶数位》在C语言中,要交换一个整数的二进制位中的奇数位和偶数位,重点需要理解位操作,当我们谈论二进制位的奇数位和偶数位时,我们是指从右到左数的位置,本文给大家介绍了使... 目录一、问题描述二、解决思路三、函数实现四、宏实现五、总结一、问题描述使用C语言代码实现:将一个整

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Go语言中最便捷的http请求包resty的使用详解

《Go语言中最便捷的http请求包resty的使用详解》go语言虽然自身就有net/http包,但是说实话用起来没那么好用,resty包是go语言中一个非常受欢迎的http请求处理包,下面我们一起来学... 目录安装一、一个简单的get二、带查询参数三、设置请求头、body四、设置表单数据五、处理响应六、超

C语言中的浮点数存储详解

《C语言中的浮点数存储详解》:本文主要介绍C语言中的浮点数存储详解,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、首先明确一个概念2、接下来,讲解C语言中浮点型数存储的规则2.1、可以将上述公式分为两部分来看2.2、问:十进制小数0.5该如何存储?2.3 浮点

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

基于Python实现多语言朗读与单词选择测验

《基于Python实现多语言朗读与单词选择测验》在数字化教育日益普及的今天,开发一款能够支持多语言朗读和单词选择测验的程序,对于语言学习者来说无疑是一个巨大的福音,下面我们就来用Python实现一个这... 目录一、项目概述二、环境准备三、实现朗读功能四、实现单词选择测验五、创建图形用户界面六、运行程序七、

使用Go语言开发一个命令行文件管理工具

《使用Go语言开发一个命令行文件管理工具》这篇文章主要为大家详细介绍了如何使用Go语言开发一款命令行文件管理工具,支持批量重命名,删除,创建,移动文件,需要的小伙伴可以了解下... 目录一、工具功能一览二、核心代码解析1. 主程序结构2. 批量重命名3. 批量删除4. 创建文件/目录5. 批量移动三、如何安