邻接表储存图实现广度优先遍历（C++）

 目录

基本要求：

邻接表的结构体：

图的邻接表创建：

图的广度优先遍历（BFS）：

邻接表的打印输出：

完整代码：

测试数据：

结果运行：

  通过给出的图的顶点和边的信息，构建无向图的邻接表存储结构。在此基础上，从A顶点开始，对无向图进行广度优先遍历，输出遍历序列。

基本要求：

（1）从测试数据读入顶点和边信息，建立无向图邻接表存储结构；

（2）把构建好的邻接表输入显示；

（3）从A顶点开始，编写BFS广度优先遍历算法；

（4）输出广度优先遍历序列。

邻接表的结构体：

typedef char VerTexType;
typedef struct Arcnode//边节点
{
	int adjvex;//该边所指向的顶点的位置
	struct Arcnode* nextarc;//指向下一条边的指针
}Arcnode;
typedef struct vnode//顶点节点
{
	VerTexType data;//顶点信息
	Arcnode* firstarc;//指向第一条依附该顶点的边的指针
}Vnode, AdjList[MVNum];
typedef struct//图
{
	AdjList vertices;//头顶点
	int vexnum, arcnum;//图当前顶点数和边数
}ALGraph;

图的邻接表创建：

bool CreateUDG(ALGraph& G)
{
	cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数
	for (int i = 0; i < G.vexnum; i++)//输入各点，构造表头结点表
	{
		cin >> G.vertices[i].data;//输入顶点值
		G.vertices[i].firstarc = NULL;//初始化表头节点指针域
		mp[G.vertices[i].data] = 0;//辅助数组，是否访问过该点，0表示没访问过
	}
	VerTexType v1, v2;
	for (int k = 0; k < G.arcnum; k++)
	{
		cin >> v1 >> v2;//输入边相邻节点
		int i = LocateVex(G, v1);
		int j = LocateVex(G, v2);//确定v1,v2位置
		Arcnode* p1, * p2;
		p1 = new Arcnode;//生成一个新的边节点
		p1->adjvex = j;//邻节点序号为j
		p1->nextarc = G.vertices[i].firstarc;
		G.vertices[i].firstarc = p1;//将新节点插入顶点vi的边表头部
		p2 = new Arcnode;
		p2->adjvex = i;//邻接点序号为i
		p2->nextarc = G.vertices[j].firstarc;
		G.vertices[j].firstarc = p2;//将新节点插入顶点vj的表头部
	}
	return 1;
}

图的广度优先遍历（BFS）：

void BFS(ALGraph& G,VerTexType u)
{
    cout<<”BFS序列：”<<endl;
	queue<VerTexType> q;
	q.push(u);
	while (!q.empty())
	{
		u = q.front();
		q.pop();
		int i = LocateVex(G, u);//取该点的位置
		if (!mp[G.vertices[i].data])//辅助数组，是否访问过
		{
			cout << G.vertices[i].data << " ";
			mp[G.vertices[i].data] = 1;
		}
		Arcnode* p;
		p = G.vertices[i].firstarc;
		while (p != NULL)//访问该头节点的链表
		{
			if (!mp[G.vertices[p->adjvex].data])
			{
				cout << G.vertices[p->adjvex].data << " ";
				mp[G.vertices[p->adjvex].data] = 1;
				q.push(G.vertices[p->adjvex].data);
			}
			p = p->nextarc;
		}
	}
}

邻接表的打印输出：

bool Print(ALGraph& G)
{
	cout << "邻接表：" << endl;
	for (int i = 0; i < G.vexnum; i++)
	{
		cout << G.vertices[i].data << " ";
		Arcnode* p;
		p = G.vertices[i].firstarc;
		while (p != NULL)
		{
			cout << G.vertices[p->adjvex].data << " ";
			p = p->nextarc;
		}
		cout << endl;
	}
	return 1;
}

完整代码：

#include<queue>
#include<map>
#define MVNum 100
using namespace std;
typedef char VerTexType;
map<VerTexType,int> mp;
typedef struct Arcnode//边节点
{
	int adjvex;//该边所指向的顶点的位置
	struct Arcnode* nextarc;//指向下一条边的指针
}Arcnode;
typedef struct vnode//顶点节点
{
	VerTexType data;//顶点信息
	Arcnode* firstarc;//指向第一条依附该顶点的边的指针
}Vnode, AdjList[MVNum];
typedef struct//图
{
	AdjList vertices;//头顶点
	int vexnum, arcnum;//图当前顶点数和边数
}ALGraph;
int LocateVex(ALGraph G, VerTexType u)//取该点位置
{
	for (int i = 0; i < G.vexnum; i++)
		if (u == G.vertices[i].data) return i;
	return -1;
}
bool CreateUDG(ALGraph& G)
{
	cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数
	for (int i = 0; i < G.vexnum; i++)//输入各点，构造表头结点表
	{
		cin >> G.vertices[i].data;//输入顶点值
		G.vertices[i].firstarc = NULL;//初始化表头节点指针域
		mp[G.vertices[i].data] = 0;
	}
	VerTexType v1, v2;
	for (int k = 0; k < G.arcnum; k++)
	{
		cin >> v1 >> v2;//输入边相邻节点
		int i = LocateVex(G, v1);
		int j = LocateVex(G, v2);//确定v1,v2位置
		Arcnode* p1, * p2;
		p1 = new Arcnode;//生成一个新的边节点
		p1->adjvex = j;//邻节点序号为j
		p1->nextarc = G.vertices[i].firstarc;
		G.vertices[i].firstarc = p1;//将新节点插入顶点vi的边表头部
		p2 = new Arcnode;
		p2->adjvex = i;//邻接点序号为i
		p2->nextarc = G.vertices[j].firstarc;
		G.vertices[j].firstarc = p2;//将新节点插入顶点vj的表头部
	}
	return 1;
}
bool Print(ALGraph& G)
{
	cout << "邻接表：" << endl;
	for (int i = 0; i < G.vexnum; i++)
	{
		cout << G.vertices[i].data << " ";
		Arcnode* p;
		p = G.vertices[i].firstarc;
		while (p != NULL)
		{
			cout << G.vertices[p->adjvex].data << " ";
			p = p->nextarc;
		}
		cout << endl;
	}
	return 1;
}
void BFS(ALGraph& G,VerTexType u)
{
    cout<<”BFS序列：”<<endl;
	queue<VerTexType> q;
	q.push(u);
	while (!q.empty())
	{
		u = q.front();
		q.pop();
		int i = LocateVex(G, u);//取该点的位置
		if (!mp[G.vertices[i].data])//辅助数组，是否访问过
		{
			cout << G.vertices[i].data << " ";
			mp[G.vertices[i].data] = 1;
		}
		Arcnode* p;
		p = G.vertices[i].firstarc;
		while (p != NULL)//访问该头节点的链表
		{
			if (!mp[G.vertices[p->adjvex].data])
			{
				cout << G.vertices[p->adjvex].data << " ";
				mp[G.vertices[p->adjvex].data] = 1;
				q.push(G.vertices[p->adjvex].data);
			}
			p = p->nextarc;
		}
	}
}
int main()
{
	ALGraph G;
	CreateUDG(G);
	Print(G);
	BFS(G, 'A');//从A开始遍历
}

测试数据：

[测试数据]

12 16

A B C D E F G H I J K L

A D

B C

B D

B F

C F

D G

E B

E F

E G

E H

F I

G K

H I

I K

J K

K L

测试数据说明：

1.第一行两个整数分别表示无向图中的顶点数m和边数n；

2.第二行中的m个整数，表示m个顶点数据元素（数据类型为字符型；

3.从第三行开始连续n行数据，每一行两个字符表示无向图中的一条边关联的两个顶点数据信息。

4.无向图如下图示：

结果运行：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/132519.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Jmeter之Bean shell使用详解

Jmeter之Bean shell使用详解

一、什么是Bean Shell BeanShell是一种完全符合Java语法规范的脚本语言,并且又拥有自己的一些语法和方法; BeanShell是一种松散类型的脚本语言(这点和JS类似); BeanShell是用Java写成的,一个小型的、免费的、可以下载的、嵌入式的Java源代码解释器,具有对象脚本语言特性,非常精…
阅读更多...
Android---内存泄漏的优化

Android---内存泄漏的优化

内存泄漏是一个隐形炸弹&#xff0c;其本身并不会造成程序异常&#xff0c;但是随着量的增长会导致其他各种并发症&#xff1a;OOM&#xff0c;UI 卡顿等。 为什么要将 Activity 单独做预防&#xff1f; 因为 Activity 承担了与用户交互的职责&#xff0c;因此内部需要持有大…
阅读更多...
JAVA基础语法编程详解

JAVA基础语法编程详解

1 类型转换 描述&#xff1a; 设计一个方法&#xff0c;将一个小于2147483647的double类型变量以截断取整方式转化为int类型输入描述&#xff1a; 随机double类型变量输出描述&#xff1a; 转化后的int类型变量示例 输入&#xff1a;123.45 输出&#xff1a; 123 题解思路&…
阅读更多...
吴恩达《机器学习》8-1-＞8-2:非线性假设、神经元和大脑

吴恩达《机器学习》8-1-＞8-2:非线性假设、神经元和大脑

一、非线性假设 在之前学到的线性回归和逻辑回归中&#xff0c;存在一个缺点&#xff0c;即当特征数量很多时&#xff0c;计算的负荷会变得非常大。考虑一个例子&#xff0c;假设我们使用 &#x1d465;₁, &#x1d465;₂ 的多项式进行预测&#xff0c;这时我们可以很好地应…
阅读更多...
【自定义类型：结构体】

【自定义类型：结构体】

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 目录 前言 1. 结构体类型的声明 1.1 结构体的概念 1.2 结构的声明 ​编辑 1.3 特殊的声明 1.4 结构的自引用 2. 结构体变量的创建和初始化 3. 结构成员访问操作符 4. 结构体内…
阅读更多...
数据库01-慢查询优化

数据库01-慢查询优化

目录 MySQL优化 慢查询 如何定位慢查询&#xff1f; 如何分析慢查询&#xff1f; MySQL优化 MySQL 优化是数据库管理和应用性能调优的一个重要方面。以下是一些常规性的 MySQL 优化经验和适用场景&#xff1a; 索引优化&#xff1a; 确保表的字段上有适当的索引&#xff0…
阅读更多...
如何选择一个可靠的爬虫代理服务商？技术人员都需要知道

如何选择一个可靠的爬虫代理服务商？技术人员都需要知道

我身边从事大数据相关行业的朋友最近告诉我&#xff0c;自己新招的小伙伴工作效率很低&#xff0c;很多最基础的工具都不会选择&#xff0c;经常因为代理IP不可靠导致工作出错。 听完这些我才意识到&#xff0c;在这个大数据时代&#xff0c;还是有很多新手在进行网络爬取任务…
阅读更多...
threejs(11)-精通着色器编程（难点）2

threejs(11)-精通着色器编程（难点）2

一、shader着色器编写高级图案 小日本国旗 precision lowp float; varying vec2 vUv; float strength step(0.5,distance(vUv,vec2(0.5))0.25) ; gl_FragColor vec4(strength,strength,strength,strength);绘制圆 precision lowp float; varying vec2 vUv; float strength 1…
阅读更多...
Java中Enum枚举类型在项目中应用

Java中Enum枚举类型在项目中应用

1、什么是枚举类型&#xff1f; 1、枚举的本质就是穷举法&#xff0c;将可能会出现的情况&#xff0c;都列举出来&#xff0c;然后在列举的情况中调用。 2、枚举与class类似&#xff0c;也可以定义属性&#xff0c;构造方法&#xff0c;有getter和setter方法。 3、枚举类型对…
阅读更多...
改进YOLOv8：结合ICCV2023｜动态蛇形卷积，构建不规则目标识别网络

改进YOLOv8：结合ICCV2023｜动态蛇形卷积，构建不规则目标识别网络

🔥🔥🔥 提升多尺度、不规则目标检测，创新提升 🔥🔥🔥 🔥🔥🔥 捕捉图像特征和处理复杂图像特征 🔥🔥🔥 👉👉👉: 本专栏包含大量的新设计的创新想法，包含详细的代码和说明，具备有效的创新组合，可以有效应用到改进创新当中 👉👉👉: �…
阅读更多...
基于FPGA的PS端的Si5340的控制

基于FPGA的PS端的Si5340的控制

1、功能 Si5340/41-D可以输出任意频率&#xff0c;当然有范围&#xff0c;100Hz1GHz。外部输入为24M或者4854M的XTAL&#xff0c;VCO在13500~14256Mhz之间&#xff0c;控制接口采用IIC或者SPI。 芯片架构图 2、IIC控制方式 3、直接上控制代码 使用米联客ZU3EG&#xff0c;将…
阅读更多...
spider-node-初识

spider-node-初识

spider-node spider想解决的问题1&#xff1a;业务架构层面2&#xff1a;代码层面3&#xff1a;业务&#xff0c;产品&#xff0c;研发&#xff0c;测试之间4: 系统迭代成本高 spider-node 配置讲解spider-node启动 spider想解决的问题 1&#xff1a;业务架构层面 帮助研发团队…
阅读更多...
C++学习笔记（一）：安装VisualStudio和Vcpkg

C++学习笔记（一）：安装VisualStudio和Vcpkg

VisualStudio安装 error C4996: ‘scanf’: This function or variable may be unsafe. Consider using scanf_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details. #include <stdio.h>int main() {printf("hello"…
阅读更多...
如何使用pngPackerGUI_V2.0，将png图片打包成plist的工具

如何使用pngPackerGUI_V2.0，将png图片打包成plist的工具

pngPackerGUI_V2.0&#xff0c;此软件是在pngpacker_V1.1软件基础之后&#xff0c;开发的界面化操作软件&#xff0c;方便不太懂命令行的小白快捷上手使用。 具体的使用步骤如下&#xff1a; 1.下载并解压缩软件&#xff0c;得到如下目录&#xff0c;双击打开 pngPackerGUI.e…
阅读更多...
iPhone或在2024开放第三方应用商店。

iPhone或在2024开放第三方应用商店。

iPhone或开放第三方应用商店&#xff0c;可以说这是一个老生常谈的话题。对于像是iOS这样封闭的系统来说&#xff0c;此前传出苹果可能开放侧载消息的时候&#xff0c;又有谁能信&#xff0c;谁会信&#xff1f; 如果是按照苹果自身的意愿&#xff0c;这种事情自然是不可能发生…
阅读更多...
Windows下Python及Anaconda的安装与设置、代码执行之保姆指南

Windows下Python及Anaconda的安装与设置、代码执行之保姆指南

学习Python编程需要安装基本的开发环境。 &#xff08;1&#xff09;python ——编译器&#xff1b;这个是任何语言都需要的&#xff1b;必需&#xff01; &#xff08;2&#xff09;Anaconda ——主要的辅助工具&#xff0c;号称是 Python‘OS&#xff1b;必需&#xff01; …
阅读更多...
LeetCode | 234. 回文链表

LeetCode | 234. 回文链表

LeetCode | 234. 回文链表 O链接 这里的解法是先找到中间结点然后再将中间节点后面的节点逆序一下然后再从头开始和从中间开始挨个比较如果中间开始的指针到走最后都相等&#xff0c;就返回true&#xff0c;否则返回false 代码如下&#xff1a; struct ListNode* reverseLis…
阅读更多...
杂记杂记杂记

杂记杂记杂记

目录 Mybatis分页插件原理&#xff1f; ThreadLocal? 树形表的标记字段是什么&#xff1f;如何查询MySQL树形表&#xff1f; Mybatis的ResultType和ResultMap的区别&#xff1f; #{}和${}有什么区别&#xff1f; 系统如何处理异常&#xff1f; Mybatis分页插件原理&#…
阅读更多...
PostMan授权认证使用

PostMan授权认证使用

Authorization 对于很多应用&#xff0c;出于安全考虑我们的接口并不希望对外公开。这个时候就需要使用授权(Authorization)机制。 授权过程验证您是否具有访问服务器所需数据的权限。 当发送请求时&#xff0c;通常必须包含参数&#xff0c;以确保请求具有访问和返回所需数据…
阅读更多...
Linux环境搭建和基础指令（一）

Linux环境搭建和基础指令（一）

&#x1f396;️&#x1f396;️&#x1f396;️&#x1f396;️&#x1f396;️&#x1f396;️&#x1f396;️&#x1f396;️&#x1f396;️&#x1f396;️&#x1f396;️&#x1f396;️&#x1f396;️&#x1f396;️&#x1f396;️&#x1f396;️&#x1f396;️&…
阅读更多...
最新文章

Copyright @ 2022~2023