当前位置: 首页 > news >正文

C++实现图的存储和遍历

前言

        许多新手友友在初学算法和数据结构时,会被图论支配过。我这里整理了一下图论常见的存储和遍历方式,仅供参考。如有问题,欢迎大佬们批评指正。

        存储我将提到四种方式:邻接矩阵、vector实现邻接表、数组模拟单链表实现的前向星实现邻接表、结构体数组直接存储边。遍历我将提到三种方式:dfs、bfs、按照边的权重值大小遍历输出。

一、邻接矩阵

#include <iostream>
#include <cstring>
#include <queue>
#include <functional>
constexpr int MAX_N = 1e3+5;
int g[MAX_N][MAX_N];
bool vis[MAX_N];
int main(){//取消同步流,加快输入输出 std::cin.tie(nullptr)->sync_with_stdio(false);//图的存储方式 1:邻接矩阵int n;std::cin >> n;for(int i = 1;i<=n;++i){for(int j = 1;j<=n;++j){std::cin >> g[i][j];}}//邻接矩阵的 dfs遍历memset(vis,false,sizeof vis);vis[1] = true;using Dfs = std::function<void(int)>;//目的是为了让 dfs函数可以进行递归 Dfs dfs = [&](int u)->void{//lambda表达式(函数) std::cout << u << ' ';for(int i = 1;i<=n;++i){if(!vis[i]&&g[u][i]){vis[i]=true;dfs(i);}}};dfs(1);std::cout << '\n';//邻接矩阵的 bfs遍历auto bfs = [&]()->void{memset(vis,false,sizeof vis);std::queue<int> q;q.emplace(1);//emplace取代 push,可以加快运行速度 vis[1] = true;while(!q.empty()){auto t = q.front();q.pop();std::cout << t << ' ';for(int i = 1;i<=n;++i){if(!vis[i]&&g[t][i]){vis[i] = true;q.emplace(i);}}}};bfs();std::cout << '\n';return 0;
}

        测试

二、 vector实现邻接表

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
constexpr int MAX_N = 1e3+5,MAX_M = 1e6+5;
std::vector<std::pair<int,int>> edges[MAX_N];
bool vis[MAX_N];
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);//图的存储方式 2:vector实现邻接表 int n,m;std::cin >> n >> m;while(m--){int x,y,w;std::cin >> x >> y >> w;//假设没有重边,无向边需要加两条边edges[x].emplace_back(y,w);edges[y].emplace_back(x,w);}//vector实现邻接表的 dfs遍历memset(vis,false,sizeof vis);vis[1] = true;using Dfs = std::function<void(int)>;Dfs dfs = [&](int u)->void{std::cout << u << ' ';for(int i = 0;i<edges[u].size();++i){if(!vis[edges[u][i].first]){vis[edges[u][i].first]=true;dfs(edges[u][i].first);}}};dfs(1);std::cout << '\n';//vector实现邻接表的 bfs遍历auto bfs = [&]()->void{memset(vis,false,sizeof vis);std::queue<int> q;q.emplace(1);vis[1] = true;while(!q.empty()){auto t = q.front();q.pop();std::cout << t << ' ';for(int i = 0;i<edges[t].size();++i){if(!vis[edges[t][i].first]){vis[edges[t][i].first] = true;q.emplace(edges[t][i].first);}}}};bfs();std::cout << '\n';return 0;
}

        测试

三、 数组模拟单链表实现的前向星实现邻接表

#include <iostream>
#include <cstring>
#include <queue>
#include <functional>
constexpr int MAX_N = 1e3+5,MAX_M = 1e6+5;
//h数组为头节点,值表示下一个节点的下标,值为 -1则表示指向 NULL(nullptr)
//有 idx到 e[idx]的边,权值为 w[idx],ne[idx]是 idx的下一个节点的下标 
int h[MAX_N],e[MAX_M],w[MAX_M],ne[MAX_M],idx;
bool vis[MAX_N];
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);//图的存储方式 3:前向星实现邻接表//采用数组模拟单链表来实现前向星auto init = [&]()->void{memset(h,-1,sizeof h);//头结点初始值为 -1,表示 next指向 NULL(nullptr) idx = 0;//下标从 0开始 };//注意这里是头插法,遍历的时候顺序是反的//但是大多数时候求最短路或者最小生成树不关注这个顺序 auto add = [&](int x,int y,int z)->void{//先勾右链,再勾左链e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;};init();int n,m;std::cin >> n >> m;while(m--){int x,y,z;std::cin >> x >> y >> z;add(x,y,z),add(y,x,z);}//前向星实现邻接表的 dfs遍历memset(vis,false,sizeof vis);vis[1] = true;using Dfs = std::function<void(int)>;Dfs dfs = [&](int u)->void{std::cout << u << ' ';for(int i = h[u];~i;i=ne[i]){int j = e[i];if(!vis[j]){vis[j] = true;dfs(j);}} };dfs(1);std::cout << '\n';//前向星实现邻接表的 bfs遍历auto bfs = [&]()->void{memset(vis,false,sizeof vis);std::queue<int> q;q.emplace(1);vis[1] = true;while(!q.empty()){auto t = q.front();q.pop();std::cout << t << ' ';for(int i = h[t];~i;i=ne[i]){int j = e[i];if(!vis[j]){vis[j] = true;q.emplace(j);}}}};bfs();std::cout << '\n';return 0;
}

        测试

四、 结构体数组直接存储边

#include <iostream>
#include <vector> 
#include <cstring>
#include <queue>
#include <algorithm>
#include <functional>
constexpr int MAX_N = 1e3+5,MAX_M = 1e6+5;
struct edge{int x,y,w;//重载 <符号,方便后续的sort()排序 bool operator < (const edge& W) {return w<W.w;}//写构造函数,方便后续直接 emplace_backedge(int _x,int _y,int _w):x(_x),y(_y),w(_w){}
};
std::vector<edge> edges;
std::vector<std::pair<int,int>> new_edges[MAX_N];
int h[MAX_N],e[MAX_M],w[MAX_M],ne[MAX_M],idx;
bool vis[MAX_N];
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);//图的存储方式 4:结构体数组直接存储边int n,m;std::cin >> n >> m;while(m--){int x,y,w;std::cin >> x >> y >> w;edges.emplace_back(x,y,w);}//如果要实现 dfs和 bfs,只需把这种存边方式转换成第2或第3种即可//若要转换成第二种: for(auto &t:edges){new_edges[t.x].emplace_back(t.y,t.w);}//若要转换成第三种:auto init = [&]()->void{memset(h,-1,sizeof h);idx = 0;};auto add = [&](int x,int y,int z)->void{e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;};init();for(auto &t:edges){add(t.x,t.y,t.w),add(t.y,t.x,t.w);}//再使用任意一种方式进行 dfs或者 bfs遍历//这里以第三种存图方式为例,dfs遍历 memset(vis,false,sizeof vis);vis[1] = true;using Dfs = std::function<void(int)>;Dfs dfs = [&](int u)->void{std::cout << u << ' ';for(int i = h[u];~i;i=ne[i]){int j = e[i];if(!vis[j]){vis[j] = true;dfs(j);}} };dfs(1);std::cout << '\n';//bfs遍历auto bfs = [&]()->void{memset(vis,false,sizeof vis);std::queue<int> q;q.emplace(1);vis[1] = true;while(!q.empty()){auto t = q.front();q.pop();std::cout << t << ' ';for(int i = h[t];~i;i=ne[i]){int j = e[i];if(!vis[j]){vis[j] = true;q.emplace(j);}}}};bfs();std::cout << '\n';//按照边的权重值大小遍历输出std::sort(edges.begin(),edges.end());for(auto &t:edges){std::cout << t.x << ' ' << t.y << ' ' << t.w << '\n';}return 0;
}

        测试

相关文章:

C++实现图的存储和遍历

前言 许多新手友友在初学算法和数据结构时&#xff0c;会被图论支配过。我这里整理了一下图论常见的存储和遍历方式&#xff0c;仅供参考。如有问题&#xff0c;欢迎大佬们批评指正。 存储我将提到四种方式&#xff1a;邻接矩阵、vector实现邻接表、数组模拟单链表实现的前向星…...

AI--构建检索增强生成 (RAG) 应用程序

LLM 所实现的最强大的应用之一是复杂的问答 (Q&A) 聊天机器人。这些应用程序可以回答有关特定源信息的问题。这些应用程序使用一种称为检索增强生成 (RAG) 的技术。 典型的 RAG 应用程序有两个主要组件 索引&#xff1a;从源中提取数据并对其进行索引的管道。这通常在线下…...

QT7_视频知识点笔记_4_文件操作,Socket通信:TCP/UDP

1.事件分发器&#xff0c;事件过滤器&#xff08;重要程度&#xff1a;一般&#xff09; event函数 2.文件操作&#xff08;QFile&#xff09; 实现功能&#xff1a;点击按钮&#xff0c;弹出对话框&#xff0c;并且用文件类读取出内容输出显示在控件上。 #include <QFi…...

智慧社区管理系统:打造便捷、安全、和谐的新型社区生态

项目背景 在信息化、智能化浪潮席卷全球的今天&#xff0c;人们对于生活品质的需求日益提升&#xff0c;期待居住环境能与科技深度融合&#xff0c;实现高效、舒适、安全的生活体验。在此背景下&#xff0c;智慧社区管理系统应运而生&#xff0c;旨在借助现代信息技术手段&…...

CustomTkinter:便捷美化Tkinter的UI界面(附模板)

CustomTkinter是一个基于Tkinter的Python用户界面库。 pip3 install customtkinter它提供了各种UI界面常见的小部件。这些小部件可以像正常的Tkinter小部件一样创建和使用&#xff0c;也可以与正常的Tkinter元素一起使用。 它的优势如下&#xff1a; CustomTkinter的小部件和…...

使用MicroPython和pyboard开发板(15):使用LCD和触摸传感器

使用LCD和触摸传感器 pybaord的pyb对LCD设备也进行了封装&#xff0c;可以使用官方的LCD显示屏。将LCD屏连接到开发板&#xff0c;连接后。 使用LCD 先用REPL来做个实验&#xff0c;在MicroPython提示符中输入以下指令。请确保LCD面板连接到pyboard的方式正确。 >>…...

c++20 std::jthread 源码简单赏析与应用

std::jthread 说明&#xff1a; std::jthread 是 C20 中引入的一个新特性&#xff0c;它是线程库中的一个类&#xff0c;专门用于处理 std::thread 与 std::stop_token 和 std::stop_source 之间的交互&#xff0c;以支持更优雅和安全的线程停止机制。 std::stop_source控制…...

自动化测试里的数据驱动和关键字驱动思路的理解

&#x1f345; 视频学习&#xff1a;文末有免费的配套视频可观看 &#x1f345; 点击文末小卡片&#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 初次接触自动化测试时&#xff0c;对数据驱动和关键字驱动不甚理解&#xff0c;觉得有点故弄玄须…...

【30天精通Prometheus:一站式监控实战指南】第6天:mysqld_exporter从入门到实战:安装、配置详解与生产环境搭建指南,超详细

亲爱的读者们&#x1f44b;   欢迎加入【30天精通Prometheus】专栏&#xff01;&#x1f4da; 在这里&#xff0c;我们将探索Prometheus的强大功能&#xff0c;并将其应用于实际监控中。这个专栏都将为你提供宝贵的实战经验。&#x1f680;   Prometheus是云原生和DevOps的…...

浅析智能体开发(第二部分):智能体设计模式和软件架构

大语言模型&#xff08;LLM&#xff09;驱动的智能体&#xff08;AI Agent&#xff09;展现出许多传统软件所不具备的特征。不仅与传统软件的设计理念、方法、工具和技术栈有显著的差异&#xff0c;AI原生&#xff08;AI Native&#xff09;的智能体还融入了多种新概念和技术。…...

Unity学习笔记---Transform组件

组件介绍 Transform组件在每个游戏对象中都存在&#xff0c;且只存在一个。该组件保存了游戏对象的位置、平移、旋转、缩放等信息。 组件相关方法 //获取当前游戏对象的Transform组件this.transform; getObject.transform; GetComponent<Transform>();//属性 gameObje…...

springboot+jsp校园理发店美容美发店信息管理系统0h29g

前台管理:会员管理、会员预定、开单点单、收银结帐、技师提成 后台管理:数据维护、物料管理、数据查询、报表分析、系统设置等 灵活的付款方式&#xff0c;支持现金、挂帐、会员卡&#xff0c;同时支持多种折扣方式并可按用户要求设置多种结帐类型善的充值卡管理模块:支持优惠卡…...

css - sass or scss ?

总的来说&#xff0c;Sass 和 SCSS 提供的功能是一样的&#xff0c;选择哪种语法主要取决于你的个人或团队的偏好。...

html5 笔记01

01 表单类型和属性 input的type属性 单行文本框: typetext 电子邮箱 : typeemail 地址路径 : type url 定义用于输入数字的字段: typenumber 手机号码: typetel 搜索框 : typesearch 定义颜色选择器 : typecolor 滑块控件 : typerange 定义日期 :typedate 定义输入时间的控件…...

E5063A是德科技e5063a网络分析仪

181-2461-8938产品概述&#xff1a; 简  述&#xff1a; E5063A 是低成本网络分析仪&#xff0c;可提供优化的性能和功能&#xff0c;适用于测试简单的无源器件&#xff0c;例如天线、电缆、滤波器和 PCB 等。它利用工业标准 ENA 系列始终如一的测量架构&#xff0c;能够极…...

【星海随笔】微信小程序(二)

WXML 模板语法 - 数据绑定 在data中定义页面的数据 在页面对应的 .js 文件中&#xff0c;把数据定义到 data 对象中即可&#xff1a; Page({data: {// 字符串类型的数据info: init data,// 数据类型的数据msgList: [{msg: hello},{msg: world}]} })Mustache 语法的格式 把 …...

Python采集安居客租房信息

Python采集安居客租房信息 一、需求介绍二、完整代码一、需求介绍 本次采集的需求就是获取到页面中的所有信息: 将数据采集好之后保存为如下csv文件: 爬取的流程不再展开分析,完整代码附后。 二、完整代码 import csvimport requests from lxml import etreeclass Anju…...

Rust构造JSON和解析JSON

目录 一、Rust构造JSON和解析JSON 二、知识点 serde_json JSON 一、Rust构造JSON和解析JSON 添加依赖项 cargo add serde-json 代码&#xff1a; use serde_json::{Result, Value};fn main() -> Result<()>{//构造json结构 cpu_loadlet data r#"{"…...

Linux 信号捕捉与处理

&#x1f493;博主CSDN主页:麻辣韭菜&#x1f493;   ⏩专栏分类&#xff1a;Linux知识分享⏪   &#x1f69a;代码仓库:Linux代码练习&#x1f69a;   &#x1f339;关注我&#x1faf5;带你学习更多Linux知识   &#x1f51d; ​ 目录 前言 1. 信号的处理时机 1.1用户…...

桂林电子科技大学计算机工程学院、广西北部湾大学计信学院莅临泰迪智能科技参观交流

5月18日&#xff0c;桂林电子科技大学计算机工程学院副院长刘利民、副书记杨美娜、毕业班辅导员黄秀娟、广西北部湾大学计信学院院长助理刘秀平莅临广东泰迪智能科技股份有限公司产教融合实训基地参观交流。泰迪智能科技副总经理施兴、广西分公司郑廷和、梁霜、培训业务部孙学镂…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践

作者&#xff1a;吴岐诗&#xff0c;杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言&#xff1a;融合数据湖与数仓的创新之路 在数字金融时代&#xff0c;数据已成为金融机构的核心竞争力。杭银消费金…...

从物理机到云原生:全面解析计算虚拟化技术的演进与应用

前言&#xff1a;我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM&#xff08;Java Virtual Machine&#xff09;让"一次编写&#xff0c;到处运行"成为可能。这个软件层面的虚拟化让我着迷&#xff0c;但直到后来接触VMware和Doc…...

Android写一个捕获全局异常的工具类

项目开发和实际运行过程中难免会遇到异常发生&#xff0c;系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler&#xff0c;它是Thread的子类&#xff08;就是package java.lang;里线程的Thread&#xff09;。本文将利用它将设备信息、报错信息以及错误的发生时间都…...

Spring Boot + MyBatis 集成支付宝支付流程

Spring Boot MyBatis 集成支付宝支付流程 核心流程 商户系统生成订单调用支付宝创建预支付订单用户跳转支付宝完成支付支付宝异步通知支付结果商户处理支付结果更新订单状态支付宝同步跳转回商户页面 代码实现示例&#xff08;电脑网站支付&#xff09; 1. 添加依赖 <!…...