算法与数据结构(十)--图的入门
一.图的定义和分类
定义:图是由一组顶点和一组能够将两个顶点连接的边组成的。
特殊的图:
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接收前端请求体的方式 请求体…...
私有化部署即时通讯平台,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作为控制器方法的形参,此时HttpServletRequest类型的参数表示封装了当前请求的请求报文的对象 index.html <form th:action"{/test/param}" method"post">用户名&#…...
TC1016-同星4路CAN(FD),2路LIN转USB接口卡
TC1016是同星智能推出的一款多通道CAN(FD)和LIN总线接口设备,CANFD总线速率最高支持8M bps,LIN支持速率0~20K bps,产品采用高速USB2.0接口与PC连接,Windows系统免驱设计使得设备具备极佳的系统兼容性。 支…...
Android源码——从Looper看ThreadLocal
1 概述 ThreadLocal用于在当前线程中存储数据,由于存储的数据只能在当前线程内使用,所以自然是线程安全的。 Handler体系中,Looper只会存在一个实例,且只在当前线程使用,所以使用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 函数,但可以自己建立一个存储过程,将具有固定分隔符的字符串转成多行。之所以不能使用自定义函数实现此功能,是因为 MySQL 的自定义函数自能返回标量值,不能返回多行结果集。 MySQL 8: drop pr…...
专题-【十字链表】
有向图的十字链表表示法:...
微信小程序教学系列(2)
第二章:小程序开发基础 1. 小程序页面布局与样式 在小程序开发中,我们可以使用 WXML(WeiXin Markup Language)和 WXSS(WeiXin Style Sheet)来定义页面的布局和样式。 1.1 WXML基础 WXML 是一种类似于 H…...
社科院与美国杜兰大学金融管理硕士项目——畅游于金融世界
随着社会经济的不断发展,职场竞争愈发激烈,很多同学都打算通过报考研究生来实现深造,提升自己的综合能力和竞争优势,获得优质的证书。而对于金融专业的学生和在职人员来说,社科院与美国杜兰大学金融管理硕士项目是一个…...
功能强大、超低功耗的STM32WL55JCI7、STM32WL55CCU7、STM32WL55CCU6 32位无线远距离MCU
STM32WL55xx 32位无线远距离MCU嵌入了功能强大、超低功耗、符合LPWAN标准的无线电解决方案,可提供LoRa、(G)FSK、(G)MSK和BPSK等各种调制。STM32WL55xx无线MCU的功耗超低,基于高性能Arm Cortex-M4 32位RISC内核(工作频率高达48MHz)…...
【自适应稀疏度量方法和RQAM】疏度测量、RQAM特征、AWSPT和基于AWSPT的稀疏度测量研究(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&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 () 是对一个查询子句做别名,同时数据库会对…...
常见前端面试之VUE面试题汇总三
7. Vue 中封装的数组方法有哪些,其如何实现页面更新 在 Vue 中,对响应式处理利用的是 Object.defineProperty 对数据进 行拦截,而这个方法并不能监听到数组内部变化,数组长度变化,数 组的截取变化等,所以需…...
AMD Ryzen硬件调试终极指南:深入SMU Debug Tool的完整实战应用
AMD Ryzen硬件调试终极指南:深入SMU Debug Tool的完整实战应用 【免费下载链接】SMUDebugTool A dedicated tool to help write/read various parameters of Ryzen-based systems, such as manual overclock, SMU, PCI, CPUID, MSR and Power Table. 项目地址: ht…...
告别繁琐操作:一键下载国家中小学智慧教育平台电子课本的智能解决方案
告别繁琐操作:一键下载国家中小学智慧教育平台电子课本的智能解决方案 【免费下载链接】tchMaterial-parser 国家中小学智慧教育平台 电子课本下载工具,帮助您从智慧教育平台中获取电子课本的 PDF 文件网址并进行下载,让您更方便地获取课本内…...
实战指南:5分钟掌握ImageToSTL图片转3D模型技术
实战指南:5分钟掌握ImageToSTL图片转3D模型技术 【免费下载链接】ImageToSTL This tool allows you to easily convert any image into a 3D print-ready STL model. The surface of the model will display the image when illuminated from the left side. 项目…...
Taotoken提供的审计日志功能如何满足企业级安全与合规需求
🚀 告别海外账号与网络限制!稳定直连全球优质大模型,限时半价接入中。 👉 点击领取海量免费额度 Taotoken提供的审计日志功能如何满足企业级安全与合规需求 1. 企业引入大模型能力后的审计挑战 当企业将大模型API能力整合到内部…...
Sketch Find and Replace插件终极指南:如何快速批量替换设计文本
Sketch Find and Replace插件终极指南:如何快速批量替换设计文本 【免费下载链接】Sketch-Find-And-Replace Sketch plugin to do a find and replace on text within layers 项目地址: https://gitcode.com/gh_mirrors/sk/Sketch-Find-And-Replace 你是否曾…...
Unity游戏马赛克移除终极指南:如何轻松解锁隐藏内容?
Unity游戏马赛克移除终极指南:如何轻松解锁隐藏内容? 【免费下载链接】UniversalUnityDemosaics A collection of universal demosaic BepInEx plugins for games made in Unity3D engine 项目地址: https://gitcode.com/gh_mirrors/un/UniversalUnity…...
jQuery WeUI移动端UI组件库架构解析与实现原理深度指南
jQuery WeUI移动端UI组件库架构解析与实现原理深度指南 【免费下载链接】jquery-weui 由于前端业界早已以React/Vue/Angular为主,个人也多年未使用过jQuery,此仓库已不再维护。推荐大家尽快转向 AntD、Element等更先进的UI库,https://ant.des…...
FPGA边缘视觉方案解析:从芯片选型到多传感器融合实战
1. 项目概述:单芯片FPGA嵌入式视觉与融合分析方案 最近在梳理一些老项目的技术文档时,翻到了Altera(现在已是Intel PSG的一部分)和Eutecus在2015年左右合作推出的一套方案,当时在EE Times上被称作“Single-Chip FPGA-B…...
OpenClaw与Cursor双向集成:打造AI驱动的自动化工作流
1. 项目概述:当OpenClaw遇上Cursor,一个双向赋能的AI大脑诞生如果你正在寻找一种方法,让你在Slack、飞书等协作工具里聊天的同时,能无缝调用一个强大的AI来帮你写代码、查文档、甚至操作GitHub,那么openclaw-cursor-br…...
R3nzSkin内存换肤技术实现与国服应用实践
R3nzSkin内存换肤技术实现与国服应用实践 【免费下载链接】R3nzSkin-For-China-Server Skin changer for League of Legends (LOL) 项目地址: https://gitcode.com/gh_mirrors/r3/R3nzSkin-For-China-Server R3nzSkin是一款专为中国服务器优化的英雄联盟内存换肤工具&am…...
