程序员经验分享-hwhale

数据结构——广度优先遍历（队列）

2023-10-26

 

队列的基本操作：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXQSIZE 100//最大队列长度
typedef int QElemType;
 
typedef struct {
	QElemType *data; //指向队列储存空间
	int front; //队首下标
	int rear;  //队尾下标
} SqQueue;
 
int InitQueue(SqQueue *Q) {//初始化队列函数，初始化成功返回1，失败返回0
	Q->data = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType)); //动态分配内存 
	if (Q->data != NULL) {  
		Q->front = Q->rear = 0;  //初始化，空队列操作，队首=队尾 
		return 1;
	}
	return 0;
}
 
void DestroyQueue(SqQueue *Q) { //销毁队列函数
	if (Q->data != NULL)
		free(Q->data); //释放队列Q的数据域 
}
 
void ClearQueue(SqQueue *Q) { //清空队列函数 
	//这里其实只需要把指针重新归位就好了，其他的数据会被后来的数据覆盖掉
	Q->rear = Q->front; 
}
 
int QueueEmpty(SqQueue Q) { //判断是否为空,为空返回1，非空返回0
	if (Q.front == Q.rear)
		return 1;
	else
		return 0;
}
 
int QueueFull(SqQueue Q) { //队列是否为满,已满返回1，未满返回0
	if ((Q.rear + 1) % MAXQSIZE == Q.front)  //队尾加一（因为位置下标从0开始）%最大长度=队首，为满 
		return 1;
	else
		return 0;
}
 
int QueueLength(SqQueue Q) {//返回队列长度
	int count = 0;
	while (Q.front != Q.rear) {
		if (Q.front >= MAXQSIZE)
			Q.front -= MAXQSIZE;
		Q.front++;//队首叠加 
		count++; //计数器叠加 
	}
	return count;
}
 
QElemType GetHead(SqQueue Q) { //若队列非空，返回队列首的值
	int e;
	if (QueueEmpty(Q) != 1) {
		e = Q.data[Q.front + 1];  //返回队首的数据域 
		return e;
	} else
		printf("队列为空！\n");
}
 
void EnQueue(SqQueue *Q, QElemType e) { //将e元素插入队列
	if (QueueFull(*Q) == 1) {
		printf("队列已满，无法添加！\n");
		return;
	} else {
		Q->rear = (Q->rear + 1) % MAXQSIZE; //引入循环队列解决假上溢 
		Q->data[Q->rear] = e;
	}
}
 
QElemType DeQueue(SqQueue *Q) { //删除队头元素，并返回其值
	QElemType e;
	if (QueueEmpty(*Q) != 1) {
		e = Q->data[Q->front + 1];
		Q->front = (Q->front + 1) % MAXQSIZE;
		//这里不用对移动后的front位置上的元素做处理，就当作没有，因为如果后续有也会被覆盖
		return e;
	} else {
		printf("队列为空！\n");
	}
}

核心算法代码：

（有向图）

void BFSTraverse(VertexNode *adjList, int vertexNum, int v) { //广度优先遍历
	int visited[vertexNum];
	initvertex(vertexNum, visited);
	SqQueue Q;
	InitQueue(&Q);//初始化队列
	ArcNode *p;
	visit(adjList, v); //输出访问过的顶点信息
	visited[v] = 1;
	EnQueue(&Q, v); //将顶点v的下标入队
	while (QueueEmpty(Q) != 1) { //当队列非空时
		v = DeQueue(&Q); //将队头元素出队并送到v中
		p = adjList[v].firstEdge; //工作指针p指向顶点v的边表
		while (p != NULL) {
			//遍历该顶点的边表
			if (visited[p->adjvex] == 0) {
				visit(adjList, p->adjvex);
				visited[p->adjvex] = 1;
				EnQueue(&Q, p->adjvex); //将顶点w的下标入队
			}
			p = p->next;
		}
	}
}

（无向图）

void BFSTraverse(int arc[][MAX_VERTEX], DataType *vertex, int vertexNum, int v) {//广度优先遍历
	int visited[vertexNum];
	initvertex(vertexNum, visited);//初始化数组
	SqQueue Q;
	InitQueue(&Q);//初始化队列
	visit(vertex, v); //输出访问过的顶点信息
	visited[v] = 1;
	EnQueue(&Q, v); //将顶点v的下标入队
	while (QueueEmpty(Q) != 1) { //当队列非空时
		v = DeQueue(&Q); //将队头元素出队并送到v中
		for (int w = 0; w < vertexNum; w++) { //将该顶点的所有连接点都扫描一遍
			if (arc[v][w] == 1 && visited[w] == 0) {
				visit(vertex, w);
				visited[w] = 1;
				EnQueue(&Q, w); //将顶点w的下标入队
			}
		}
	}
}

 有向图（邻接表）：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "循环队列.h"
#define MAX_VERTEX 10//最大的顶点个数
typedef char DataType;
 
/*
当DataType为char时要特别注意输入时空格和换行符，分别利用getchar()
和fflush(stdin);来清空内存区
*/
typedef struct ArcNode { /*边表结点*/
	int adjvex;//边表数据域，即下标
	struct ArcNode *next; //指针域
} ArcNode;
 
typedef struct VertexNode { /*顶点表结点*/
	DataType vertex;//顶点的数据
	ArcNode *firstEdge; //指向储存该顶点所连接所有结点的边表
} VertexNode;
void initVertex(DataType *, int);
 
//以下是有向图的定义
void ALGraph(DataType *vertex, VertexNode *adjList, int vertexNum, int arcNum) { //初始化构造图（邻接表法）
	int vi, vj;                                                     //顶点的数据，顶点表结点，队列，顶点最大长度，边表最大长度 
	int count = 0;
	initVertex(vertex, vertexNum); // 输入函数（顶点，顶点表结点最大长度） 
	for (int i = 0; i < vertexNum; i++) { //初始化顶点表
		adjList[i].vertex = vertex[i];  //把数据弄进队列的数据域 
		adjList[i].firstEdge = NULL; //第一个结点数据域初始化赋空值 
	}
	for (int i = 0; i < arcNum; i++) { 
		//输入边的信息储存在边表中
		printf("请输入第%d条边依附的两个顶点的编号(方向->)：", count++);
		fflush(stdin);//清除输入缓冲区（否则这里就会直接跳过scanf）
		scanf("%d %d", &vi, &vj); //输入该边依附的顶点的编号
		ArcNode *s;
		s = (ArcNode *)malloc(sizeof(ArcNode));
		if (s != NULL) {
			s->adjvex = vj;
			s->next = adjList[vi].firstEdge; //头插法建立链表
			adjList[vi].firstEdge = s;
		} else
			printf("init error!\n");
	}
}
 
void initVertex(DataType *vertex, int vertexNum) {//输入函数
	printf("请逐个输入顶点的内容：");
	DataType x;
	for (int i = 0; i < vertexNum; i++) { //顶点数组赋值
		getchar();//吸收空格
		scanf("%c", &x);
		vertex[i] = x;
	}
}
 
void printALGraph(VertexNode *adjList, int vertexNum) {  //打印有向图 
	printf("vertex  firstEdge\n");
	ArcNode *p ;
	for (int i = 0; i < vertexNum; i++) {
		printf("%3c -->", adjList[i].vertex);  //打印顶点 
		p = adjList[i].firstEdge; 
		while (p != NULL) { 
			printf("%d -->", p->adjvex);  //打印顶点对应的边 
			p = p->next; // 继续循环下一个 
		}
		printf("NULL\n");
		printf("\n");
	}
}
 
int isLinked(VertexNode *adjList, int i, int j) { //判断两顶点i,j是否有边相连,1是相连，0是不相连
	ArcNode *p = adjList[i].firstEdge ;
	while (p != NULL) {
		if (p->adjvex == j)
			return 1;
		else
			p = p->next;
	}
	p = adjList[j].firstEdge;
	while (p != NULL) {
		if (p->adjvex == i)
			return 1;
		else
			p = p->next;
	}
	return 0;
}
 
int nodeDepth(VertexNode *adjList, int index, int vertexNum) { //任意一顶点的度（度就是与顶点相连的边数） 
	int count = 0;
	ArcNode *p = adjList[index].firstEdge;
	while (p != NULL) {
		count++;
		p = p->next;
	}
	return count;
}
 
void freeArcNode(VertexNode *adjList, int vertexNum) {
	ArcNode *p;
	ArcNode *temp;
	for (int i = 0; i < vertexNum; i++) {
		p = adjList[i].firstEdge ;
		while (p != NULL) {
			temp = p;
			p = p->next;
			free(temp);
		}
	}
}
 
void initvertex(int vertexNum, int *visited) { //初始化visited函数
	for (int i = 0; i < vertexNum; i++)
		visited[i] = 0;
}
 
void visit(VertexNode *adjList, int v) { //输出访问过的顶点信息
	printf("%c ", adjList[v].vertex);//记得改变输出时要改变数据类型
}
 
void DFSTraverse(VertexNode *adjList, int *visited, int vertexNum, int v) {//深度优先遍历
	static int flag = 0;
	if (flag == 0) {//第一次需要初始化
		initvertex(vertexNum, visited);
		flag = 1;
	}
	visit(adjList, v); //输出访问过的顶点信息
	visited[v] = 1;
	ArcNode *p = adjList[v].firstEdge;
	while (p != NULL) {
		if (visited[p->adjvex] == 0)
			DFSTraverse(adjList, visited, vertexNum, p->adjvex);
		p = p->next;
	}
}
 
void ranklist(VertexNode *adjList, int vertexNum) { //将边表进行升序的排序，便于遍历操作
	ArcNode *p, *q;
	int temp;
	for (int i = 0; i < vertexNum; i++) {
		p = adjList[i].firstEdge;
		q = p;
		while (p != NULL) {
			while (q != NULL) {
				if (p->adjvex > q->adjvex) {
					temp = p->adjvex;
					p->adjvex = q->adjvex;
					q->adjvex = temp;
				}
				q = q->next;
			}
			p = p->next;
		}
	}
}
 
void BFSTraverse(VertexNode *adjList, int vertexNum, int v) { //广度优先遍历
	int visited[vertexNum];
	initvertex(vertexNum, visited);
	SqQueue Q;
	InitQueue(&Q);//初始化队列
	ArcNode *p;
	visit(adjList, v); //输出访问过的顶点信息
	visited[v] = 1;
	EnQueue(&Q, v); //将顶点v的下标入队
	while (QueueEmpty(Q) != 1) { //当队列非空时
		v = DeQueue(&Q); //将队头元素出队并送到v中
		p = adjList[v].firstEdge; //工作指针p指向顶点v的边表
		while (p != NULL) {
			//遍历该顶点的边表
			if (visited[p->adjvex] == 0) {
				visit(adjList, p->adjvex);
				visited[p->adjvex] = 1;
				EnQueue(&Q, p->adjvex); //将顶点w的下标入队
			}
			p = p->next;
		}
	}
}

测试主函数：

#include "图_邻接表.h"
 
int main() {
	DataType vertex[MAX_VERTEX];//储存所有的顶点
	int vertexNum, arcNum; //结点个数，边的个数
	printf("输入顶点个数:");
	scanf("%d", &vertexNum);
	printf("输入边个数:");
	scanf("%d", &arcNum);
	VertexNode adjList[vertexNum];//顶点表
	ALGraph(vertex, adjList, vertexNum, arcNum);
	ranklist(adjList, vertexNum);
	printALGraph(adjList, vertexNum);
	printf("测试判断两顶点是否相连，请输入两个顶点下标:");
	int i, j;
	scanf("%d %d", &i, &j);
	if (isLinked(adjList, i, j) == 1)
		printf("相连！\n");
	else
		printf("不相连！\n");
	printf("测试求顶点的度，请输入一个顶点下标:");
	int index;
	scanf("%d", &index);
	printf("该顶点的度为:%d\n", nodeDepth(adjList, index, vertexNum));
	printf("-----------------测试邻接表的深度优先遍历-----------------\n");
	printf("\n");
	int visited[vertexNum];//判断结点是否访问过，访问过设置1，未访问过为0
	int v;
	printf("请输入深度优先遍历的第一个结点编号:");
	scanf("%d", &v);
	printf("深度优先遍历序列:");
	DFSTraverse(adjList, visited, vertexNum, v);
	printf("\n");
	printf("\n");
	printf("-----------------测试邻接表的广度优先遍历-----------------\n");
	printf("\n");
	printf("请输入广度优先遍历的第一个结点编号:");
	scanf("%d", &v);
	printf("广度优先遍历序列:");
	BFSTraverse(adjList, vertexNum, v);
	freeArcNode(adjList, vertexNum);
}

无向图（邻接矩阵）：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "循环队列.h"
#define MAX_VERTEX 10//最大的顶点个数
typedef int DataType;
 
//以下是无向图的定义
void MGraph(DataType *vertex, int arc[][MAX_VERTEX], int vertexNum, int arcNum) { //初始化构造图（邻接矩阵法）
	printf("请逐个输入顶点的内容：");
	DataType x;
	DataType vi, vj; //构建邻接矩阵时，一条边的两个结点编号
	for (int i = 0; i < vertexNum; i++) { //顶点数组赋值
		scanf("%d", &x);
		vertex[i] = x;
	}
	for (int i = 0; i < vertexNum; i++) //初始化邻接矩阵
		for (int j = 0; j < vertexNum; j++)
			arc[i][j] = 0;
	int count = 1;
	for (int i = 0; i < arcNum; i++) { //依次输入每一条边
		printf("请输入第%d条边依附的两个顶点的编号：", count++);
		scanf("%d %d", &vi, &vj); //输入该边依附的顶点的编号
		arc[vi][vj] = 1; //置有边标志
		arc[vj][vi] = 1;
	}
 
}
 
void printMGraph(DataType *vertex, int arc[][MAX_VERTEX], int vertexNum) { //输出
	printf("vertex:");
	for (int i = 0; i < vertexNum; i++) {
		printf("%d ", vertex[i]);
	}
	printf("\n");
	printf("arc:\n");
	for (int i = 0; i < vertexNum; i++) {
		for (int j = 0; j < vertexNum; j++) {
			if (j == vertexNum - 1)
				printf("%d\n", arc[i][j]);
			else
				printf("%d ", arc[i][j]);
		}
	}
 
}
 
int isLinked(int arc[][MAX_VERTEX], int i, int j) { //两顶点i,j是否有边相连,1是相连，0是不相连
	if (arc[i][j] == 1)
		return 1;
	else
		return 0;
}
 
int nodeDepth(int arc[][MAX_VERTEX], int index, int vertexNum) { //任意一顶点的度
	//无向图任意遍历行\列求和
	int count = 0;
	for (int i = 0; i < vertexNum; i++) {
		if (arc[index][i] == 1)
			count++;
	}
	return count;
}
 
void initvertex(int vertexNum, int *visited) { //初始化visited函数
	for (int i = 0; i < vertexNum; i++)
		visited[i] = 0;
}
 
void visit(DataType *vertex, int v) { //输出访问过的顶点信息
	printf("%d ", vertex[v]);
 
}
 
void DFSTraverse(int arc[][MAX_VERTEX], DataType *vertex, int *visited, int vertexNum,//深度优先遍历
                 int v) { //v是遍历的起始位置的编号
	static int flag = 0;
	if (flag == 0) {//第一次需要初始化
		initvertex(vertexNum, visited);
		flag = 1;
	}
	visit(vertex, v); //输出访问过的顶点信息
	visited[v] = 1;
	for (int i = 0; i < vertexNum; i++) { //因为是邻接矩阵，所以编号的顺序本来就是由小到大的.所以不用遍历找
		if (arc[v][i] != 0 && visited[i] == 0)
			DFSTraverse(arc, vertex, visited, vertexNum, i); //二维数组传参，调用时实参直接写数组名
	}
}
 
void BFSTraverse(int arc[][MAX_VERTEX], DataType *vertex, int vertexNum, int v) {//广度优先遍历
	int visited[vertexNum];
	initvertex(vertexNum, visited);//初始化数组
	SqQueue Q;
	InitQueue(&Q);//初始化队列
	visit(vertex, v); //输出访问过的顶点信息
	visited[v] = 1;
	EnQueue(&Q, v); //将顶点v的下标入队
	while (QueueEmpty(Q) != 1) { //当队列非空时
		v = DeQueue(&Q); //将队头元素出队并送到v中
		for (int w = 0; w < vertexNum; w++) { //将该顶点的所有连接点都扫描一遍
			if (arc[v][w] == 1 && visited[w] == 0) {
				visit(vertex, w);
				visited[w] = 1;
				EnQueue(&Q, w); //将顶点w的下标入队
			}
		}
	}
}

测试代码（主函数）：

#include "图_邻接矩阵.h"
 
main() {
	DataType vertex[MAX_VERTEX];//储存所有的顶点
	int arc[MAX_VERTEX][MAX_VERTEX];//邻接矩阵，结点间的连通关系
	int vertexNum, arcNum; //结点个数，边的个数
	printf("输入顶点个数:");
	scanf("%d", &vertexNum);
	printf("输入边个数:");
	scanf("%d", &arcNum);
	MGraph(vertex, arc, vertexNum, arcNum);
	printMGraph(vertex, arc, vertexNum);
	printf("测试判断两顶点是否相连，请输入两个顶点下标:");
	int i, j;
	scanf("%d %d", &i, &j);
	if (isLinked(arc, i, j) == 1)
		printf("相连！\n");
	else
		printf("不相连！\n");
	printf("测试求顶点的度，请输入一个顶点下标:");
	int index;
	scanf("%d", &index);
	printf("该顶点的度为:%d\n", nodeDepth(arc, index, vertexNum));
	printf("-----------------测试邻接矩阵的深度优先遍历-----------------\n");
	printf("\n");
	int visited[vertexNum];//判断结点是否访问过，访问过设置1，未访问过为0
	int v;
	printf("请输入深度优先遍历的第一个结点编号:");
	scanf("%d", &v);
	printf("深度优先遍历序列:");
	DFSTraverse(arc, vertex, visited, vertexNum, v);
	printf("\n");
	printf("\n");
	printf("-----------------测试邻接矩阵的广度优先遍历-----------------\n");
	printf("\n");
	printf("请输入广度优先遍历的第一个结点编号:");
	scanf("%d", &v);
	printf("广度优先遍历序列:");
	BFSTraverse(arc, vertex, vertexNum, v);
	printf("\n");
}


 

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

宽度优先

算法

数据结构——广度优先遍历（队列） 的相关文章

随机推荐

  • 2020 JAVA eclipse 中文汉化包 安装教程--傻瓜式操作

    下载的是 Eclipse IDE for Enterprise Java Developers includes Incubating components 这个版本 直接下载了 解压就可以使用 用的是官方的汉化包 下载 解压 复制 粘贴

  • 5个步骤实现软件质量的快速提升

    每个人都希望软件质量更高 速度更快 对现代软件开发团队的要求是巨大的 从竞争和市场压力的增加 功能和复杂性的增加 到对产品质量 安全性和可靠性的更高期望 敏捷开发方法常常受到追捧 因为它能更快地响应变化 更好地实现客户需求 但是 敏捷和De

  • ESXI虚拟机厚置备延迟置零转换为Thin Provision方法

    最近有博友提出一个需求 他们公司的服务器磁盘空间不足了 现在无法正常创建虚拟机 其实并没有使用到这么多空间 只是因为划了这么多空间给虚拟机 所以造成磁盘空间不足 那么是否有什么解决的方法了 详细了解发现虚拟机在配置磁盘的时候设置的是厚置备延

  • RC低通滤波器

    先来几个不错的资源链接 1 RC滤波器截止频率在线计算器 http www eechina com tools rc filter cutoff frequency html 2 详谈一阶RC低通滤波器如何过滤高频噪声 网上不错的一个帖子

  • Linux学习-43-挂载Linux系统外的文件mount和卸载文件系统umount命令用法

    10 10 mount命令详解 挂载Linux系统外的文件 所有的硬件设备必须挂载之后才能使用 新硬盘先格式化后创建分区 再对分区进行挂载 只不过 有些硬件设备 比如硬盘分区 在每次系统启动时会自动挂载 而有些 比如 U 盘 光盘 则需要手

  • 使用w,vmstat命令,top命令,sar命令,nload命令

    监控系统状态 w命令 uptime load average 0 00 0 01 0 05 上面这条显示的就是系统负载 后面有三段数字 root localhost w 21 33 04 up 41 min 1 user load aver

  • STS & 开发异常

    1 Failed to start component 情景 本地 tomcat 部署了两个项目 一个provider 一个 server 前台通过server访问 provider 在开发的时候 将tomcat部署的服务 Clean 或者

  • Android-模块化-项目实践和探索分享

    文章目录 前言 一 gradle统一配置 1 多模块项目的构建 2 根项目的构建配置 3 常用公用的构建配置 二 nexus与maven publish 1 安装nexus 2 仓库 3 maven publish 三 动态依赖 1 依赖的

  • 在IDEA中使用Maven将项目打包成jar包

    1 在pom xml文件中添加代码

  • [Python图像处理] 二十九.MoviePy视频编辑库实现抖音短视频剪切合并操作

    该系列文章是讲解Python OpenCV图像处理知识 前期主要讲解图像入门 OpenCV基础用法 中期讲解图像处理的各种算法 包括图像锐化算子 图像增强技术 图像分割等 后期结合深度学习研究图像识别 图像分类应用 希望文章对您有所帮助 如

  • 【质量】代码质量评价标准

    今天来思考下如何评价代码质量 业界公认比较认可的七大标准 可维护性 maintainability 可读性 readability 可扩展性 extensibility 灵活性 flexibility 简洁性 simplicity 可复用性

  • ReentrantReadWriteLock

    一ReentrantReadWriteLock 是Lock的另一种实现方式 我们知道ReentrantLock是一个排他锁 同一时间只允许一个线程访问 而ReentrantReadWriteLock允许多个读线程同时访问 但不允许写线程和读

  • RuntimeError: Address already in use

    Pytorch用多张GPU训练时 会报地址已被占用的错误 其实是端口号冲突了 因此解决方法要么kill原来的进程 要么修改端口号 在代码里重新配置 torch distributed init process group dist init

  • ajax异步加载jqgrid之动态创建

    2019独角兽企业重金招聘Python工程师标准 gt gt gt 之前写过一篇过于ajax异步加载jqgrid的文章 那个只是一个特殊的情况 如果创建不同数据库表的jqgrid 必须分别写servlet dao层和连接池 很麻烦 今天我写

  • Hive insert overwrite 问题

    微信公众号 苏言论 理论联系实际 畅言技术与生活 文章目录 1 测试的版本 2 insert overwrite使用说明 3 示例 4 建议的操作 5 参考链接 1 测试的版本 Apache hive 1 1 0 2 3 1 3 1 0 2

  • vue3 全局批量注册组件

    思路 1 使用 require 提供的函数 context 加载某一个目录下的所有 vue 后缀的文件 2 context 函数会返回一个导入函数 importFn 3 它有一个方法 keys 获取所有的文件路径 4 通过文件路径数组 通过

  • Ubuntu20.04 + 3090 安装nvidia驱动，附加解决重启黑屏卡在 /dev/***: clean, **files,***blocks的问题

    目录 准备 禁用nouveau 解决黑屏问题并安装驱动 参考 准备 首先需要知道当前电脑 服务器的显卡型号 这个自行查找自己电脑配置 查找显卡对应的驱动版本 通过命令ubuntu drivers devices查看当前设备所支持的驱动 带有

  • Android 监控SD卡的插拔状态

    http blog csdn net pasterzhang article details 8151877 我们是以DV6300 T的平台来做测试的 发现有2种方式来检测Android中external media 包括SD卡 USB 的

  • Spring Cloud Feign nested exception is java.lang.IllegalStateException

    Spring Cloud Feign 使用时抛出异常 nested exception is java lang IllegalStateException RequestParam value was empty on parameter

  • 数据结构——广度优先遍历（队列）

    队列的基本操作 include

热门标签