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

算法与数据结构(十)--图的入门

一.图的定义和分类

定义:图是由一组顶点和一组能够将两个顶点连接的边组成的。

特殊的图
1.自环:即一条连接一个顶点和其自身的边;
2.平行边:连接同一对顶点的两条边;

图的分类
按照连接两个顶点的边的不同,可以把图分为以下两种:
无向图:边仅仅连接两个顶点,没有其他含义;
有向图:边不仅连接两个顶点,并且具有方向;

二.无向图

1.图的相关术语

相邻顶点
当两个顶点通过一条边相连时,我们称这两个顶点是相邻的,并且称这个边依赖于这两个顶点。

某个顶点的度就是依附于该顶点的边的个数。
子图
是一幅图的所有边的子集(包含这些边依附的顶点)组成的图。
路径
是由边顺序连接的一系列的顶点组成。

是一条至少含有一条边且终点和起点相同的路径。

连通图
如果图中任一一个顶点都存在一条路径到达另外一个顶点,那么这幅图就称之为联通图。
连通子图
一个非联通图由若干连通的部分组成,每一个连通的部分都可以成为该图的连通子图。

 

2.图的存储结构

要表示一幅图,只需要表示清楚一下两部分内容即可:
1.图中所有的顶点;
2.所有连接顶点的边;
常见 图的存储结构有两种:邻接矩阵和邻接表


【1】邻接矩阵

1.使用一个V*V的二维数组int[V][V]  adj。
2.如果顶点v和顶点w相连,我们只需要把adj[v][w]和adj[w][v]的值设置为1,否则设置为0即可。

 很明显,邻接矩阵这种存储方式的空间复杂度是V^2的,如果我们处理的问题规模比较大的话,内存空间极有可能不够用。

【2】邻接表

1.使用一个大小为V的数组Queue[V]  adj,把索引看做是顶点;
2.每个索引处adj[v]存储了一个队列,该队列中存储的是所有与该顶点相邻的其他顶点

很明显,邻接表的空间并不是是线性级别的,所以后面我们一直采用邻接表这种存储形式来表示图。

三.图的实现

四.图的搜索

1.深度优先搜索

所谓的深度优先搜索,指的是在搜索时,如果遇到一个结点既有子结点,又有兄弟结点,那么先找子结点,然后找 兄弟结点。

2.广度优先搜索

所谓的广度优先搜索,指的是在搜索时,如果遇到一个结点既有子结点,又有兄弟结点,那么先找兄弟结点,然后 找子结点。

相关文章:

算法与数据结构(十)--图的入门

一.图的定义和分类 定义:图是由一组顶点和一组能够将两个顶点连接的边组成的。 特殊的图: 1.自环:即一条连接一个顶点和其自身的边; 2.平行边:连接同一对顶点的两条边; 图的分类: 按照连接两个顶点的边的…...

【Go 基础篇】Go语言 init函数详解:包的初始化与应用

介绍 在Go语言中,init() 函数是一种特殊的函数,用于在包被导入时执行一次性的初始化操作。init() 函数不需要手动调用,而是在包被导入时自动执行。这使得我们可以在包导入时完成一些必要的初始化工作,确保包的使用具有正确的环境…...

wazuh环境配置及漏洞复现

目录 一、wazuh配置 1进入官网下载OVA启动软件 2.虚拟机OVA安装 二、wazuh案例复现 1.wazuh初体验 2.这里我们以SQL注入为例,在我们的代理服务器上进行SQL注入,看wazuh如何检测和响应 一、wazuh配置 1进入官网下载OVA启动软件 Virtual Machine (O…...

Java接收前端请求体方式

💗wei_shuo的个人主页 💫wei_shuo的学习社区 🌐Hello World ! 文章目录 RequestBodyPathVariableRequestParamValidated方法参数校验方法返回值校验 RequestHeaderHttpServletRequest ## Java接收前端请求体的方式 请求体&#xf…...

私有化部署即时通讯平台,30分钟替换钉钉和企业微信

随着企业对即时通讯和协作工具的需求不断增长,私有化部署的即时通讯平台成为企业的首选。WorkPlus作为有10余年行业深耕经验与技术沉淀品牌,以其安全高效的私有化部署即时通讯解决方案,帮助企业在30分钟内替换钉钉和企业微信。本文将深入探讨…...

如何深入理解 Node.js 中的流(Streams)

Node.js是一个强大的允许开发人员构建可扩展和高效的应用程序。Node.js的一个关键特性是其内置对流的支持。流是Node.js中的一个基本概念,它能够实现高效的数据处理,特别是在处理大量信息或实时处理数据时。 在本文中,我们将探讨Node.js中的流…...

MSP430FR2xxx开发(一)添加driverlib

一、新建工程 根据自己手上的硬件型号新建工程,文中已MSP430FR2355为例。 二、添加driverlib 首先去官方下载driverlib. https://www.ti.com.cn/tool/cn/MSPDRIVERLIB?keyMatchMSP430%20DRIVERLIB#downloads 下载后的内容如下: 我这里就选择MSP430…...

【C++】做一个飞机空战小游戏(九)——发射子弹的编程技巧

[导读]本系列博文内容链接如下: 【C】做一个飞机空战小游戏(一)——使用getch()函数获得键盘码值 【C】做一个飞机空战小游戏(二)——利用getch()函数实现键盘控制单个字符移动【C】做一个飞机空战小游戏(三)——getch()函数控制任意造型飞机图标移动 【C】做一个飞…...

34.SpringMVC获取请求参数

SpringMVC获取请求参数 通过ServletAPI获取 将HttpServletRequest作为控制器方法的形参&#xff0c;此时HttpServletRequest类型的参数表示封装了当前请求的请求报文的对象 index.html <form th:action"{/test/param}" method"post">用户名&#…...

TC1016-同星4路CAN(FD),2路LIN转USB接口卡

TC1016是同星智能推出的一款多通道CAN&#xff08;FD&#xff09;和LIN总线接口设备&#xff0c;CANFD总线速率最高支持8M bps&#xff0c;LIN支持速率0~20K bps&#xff0c;产品采用高速USB2.0接口与PC连接&#xff0c;Windows系统免驱设计使得设备具备极佳的系统兼容性。 支…...

Android源码——从Looper看ThreadLocal

1 概述 ThreadLocal用于在当前线程中存储数据&#xff0c;由于存储的数据只能在当前线程内使用&#xff0c;所以自然是线程安全的。 Handler体系中&#xff0c;Looper只会存在一个实例&#xff0c;且只在当前线程使用&#xff0c;所以使用ThreadLocal进行存储。 2 存储原理 …...

16、Flink 的table api与sql之连接外部系统: 读写外部系统的连接器和格式以及JDBC示例(4)

Flink 系列文章 1、Flink 部署、概念介绍、source、transformation、sink使用示例、四大基石介绍和示例等系列综合文章链接 13、Flink 的table api与sql的基本概念、通用api介绍及入门示例 14、Flink 的table api与sql之数据类型: 内置数据类型以及它们的属性 15、Flink 的ta…...

MySQL 自定义 split 存储过程

MySQL 没有提供 split 函数&#xff0c;但可以自己建立一个存储过程&#xff0c;将具有固定分隔符的字符串转成多行。之所以不能使用自定义函数实现此功能&#xff0c;是因为 MySQL 的自定义函数自能返回标量值&#xff0c;不能返回多行结果集。 MySQL 8&#xff1a; drop pr…...

专题-【十字链表】

有向图的十字链表表示法&#xff1a;...

微信小程序教学系列(2)

第二章&#xff1a;小程序开发基础 1. 小程序页面布局与样式 在小程序开发中&#xff0c;我们可以使用 WXML&#xff08;WeiXin Markup Language&#xff09;和 WXSS&#xff08;WeiXin Style Sheet&#xff09;来定义页面的布局和样式。 1.1 WXML基础 WXML 是一种类似于 H…...

社科院与美国杜兰大学金融管理硕士项目——畅游于金融世界

随着社会经济的不断发展&#xff0c;职场竞争愈发激烈&#xff0c;很多同学都打算通过报考研究生来实现深造&#xff0c;提升自己的综合能力和竞争优势&#xff0c;获得优质的证书。而对于金融专业的学生和在职人员来说&#xff0c;社科院与美国杜兰大学金融管理硕士项目是一个…...

功能强大、超低功耗的STM32WL55JCI7、STM32WL55CCU7、STM32WL55CCU6 32位无线远距离MCU

STM32WL55xx 32位无线远距离MCU嵌入了功能强大、超低功耗、符合LPWAN标准的无线电解决方案&#xff0c;可提供LoRa、(G)FSK、(G)MSK和BPSK等各种调制。STM32WL55xx无线MCU的功耗超低&#xff0c;基于高性能Arm Cortex-M4 32位RISC内核&#xff08;工作频率高达48MHz&#xff09…...

【自适应稀疏度量方法和RQAM】疏度测量、RQAM特征、AWSPT和基于AWSPT的稀疏度测量研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

sql递归查询

一、postgresql 递归sql with recursive p as(select t1.* from t_org_test t1 where t1.id2union allselect t2.*from t_org_test t2 join p on t2.parent_idp.id) select id,name,parent_id from p; sql中with xxxx as () 是对一个查询子句做别名&#xff0c;同时数据库会对…...

常见前端面试之VUE面试题汇总三

7. Vue 中封装的数组方法有哪些&#xff0c;其如何实现页面更新 在 Vue 中&#xff0c;对响应式处理利用的是 Object.defineProperty 对数据进 行拦截&#xff0c;而这个方法并不能监听到数组内部变化&#xff0c;数组长度变化&#xff0c;数 组的截取变化等&#xff0c;所以需…...

在Nodejs后端服务中集成Taotoken调用大模型API

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 在Nodejs后端服务中集成Taotoken调用大模型API 对于Node.js后端开发者而言&#xff0c;将大模型能力集成到服务中已成为构建智能应…...

千万级用户购物车系统的架构设计

我们当时搞的购物车服务&#xff0c;其实还是有点庞大的&#xff0c;看似是一个简单的CRUD&#xff0c;但是当你真正去实现一个购物车的时候&#xff0c;发现压根不是那回事。 当商品类型从单一SKU扩展到普通商品、套餐组合、活动商品&#xff0c;拼单等混合的时候&#xff0c;…...

3大核心功能,让你的惠普OMEN游戏本性能彻底解放

3大核心功能&#xff0c;让你的惠普OMEN游戏本性能彻底解放 【免费下载链接】OmenSuperHub 使用 WMI BIOS控制性能和风扇速度&#xff0c;自动解除DB功耗限制。 项目地址: https://gitcode.com/gh_mirrors/om/OmenSuperHub 还在为惠普OMEN游戏本官方软件过于臃肿而烦恼吗…...

对比按量计费与Token Plan套餐,哪种方式更适合你的项目

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 对比按量计费与Token Plan套餐&#xff0c;哪种方式更适合你的项目 在接入大模型服务时&#xff0c;成本控制是每个开发者和团队都…...

TEdit终极教程:如何用免费地图编辑器10倍提升泰拉瑞亚创作效率

TEdit终极教程&#xff1a;如何用免费地图编辑器10倍提升泰拉瑞亚创作效率 【免费下载链接】Terraria-Map-Editor TEdit - Terraria Map Editor - TEdit is a stand alone, open source map editor for Terraria. It lets you edit maps just like (almost) paint! It also let…...

[具身智能-653]:人的大脑神经网络就是天然的模拟电路,还是数字电路?

结论先给&#xff1a;人脑神经网络&#xff0c;本质是【天然模拟电路】&#xff0c;不是数字电路这和前面聊的模拟电路频域特性、硬件隐式频域滤波完全同逻辑。一、先分清&#xff1a;数字电路 vs 模拟电路 核心区别数字电路只有0、1两种离散电平&#xff0c;跳变是阶跃式&…...

跨越版本鸿沟:Matlab 2020b与VS2022混合编译环境搭建实战

1. 环境准备&#xff1a;当Matlab 2020b遇上VS2022 第一次尝试在Matlab 2020b里调用VS2022编译器时&#xff0c;命令行弹出的红色报错让我愣了半天。官方文档明确写着Matlab 2020b最高只支持VS2019&#xff0c;这就像让Windows XP运行最新版Photoshop——理论上不可能&#xff…...

实测Taotoken平台API调用稳定性与延迟体感观察记录

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 实测Taotoken平台API调用稳定性与延迟体感观察记录 在将大模型能力集成到生产应用时&#xff0c;服务的稳定性和响应延迟是开发者关…...

太秀了,我把自己蒸馏成了 Skill!已开源

最近 GitHub 上掀起了一股「AI 蒸馏」热潮&#xff0c;这里的蒸馏可不是酿酒&#xff0c;而是把身边的人封装成 AI 技能包——同事.skill、老板.skill、搭档.skill 等各类蒸馏项目层出不穷&#xff0c;大家都在把身边人的工作经验、说话风格、做事逻辑&#xff0c;做成可直接使…...

从习题到实战:掌握随机变量及其分布的5个核心场景

1. 从杯子分球看离散型随机变量 想象你面前有4个空杯子和3个乒乓球&#xff0c;随手把球扔进杯子里会发生什么&#xff1f;这个看似简单的游戏&#xff0c;其实是理解离散型随机变量的绝佳案例。X代表"杯子中球的最大个数"&#xff0c;它可能取值为1、2、3——这就是…...