C语言的数据结构:图的基本概念

前言

之前学过了其它的数据结构,如:
集合 \color{#5ecffd}集合 集合 —— 数据元素属于一个集合。
线型结构 \color{#5ecffd}线型结构 线型结构 —— 一个对一个,如线性表、栈、队列,每一个节点和其它节点之间的关系 一个对一个 \color{orange}一个对一个 一个对一个
树型结构 \color{#5ecffd}树型结构 树型结构 —— 一个对多个,如树。

现在要接触一下图这个结构了,图是多个对多个的结构,其没有初始结点,也没有最终结点。每一个节点都称为顶点。
图 \color{#5ecffd}图 ——因为图是若干个顶点,顶点之间相互连接,没有先后顺序,所以图没有顺序存储结构,但可以借助二维数组来表示元素间的关系( 邻接矩阵 \color{orange}邻接矩阵 邻接矩阵)。链式存储结构也可以描述图: 邻接表、邻接多重表、十字链表 \color{orange}邻接表、邻接多重表、十字链表 邻接表、邻接多重表、十字链表

邻接矩阵

存储表示:用两个数组分别存储 顶点表 \color{orange}顶点表 顶点表 邻接矩阵 \color{orange}邻接矩阵 邻接矩阵

#define MAZINT 32767	//极大值
#define MVNUM 100		//最大顶点数
typedef char VerTexType;	//设顶点的数据类型为字符型
typedef int ArcType;		//假设边的权值类型为整型typedef struct {VerTexType vexs[MVNUM];		//顶点表ArcType	arcs[MVNUM][MVNUM];	//邻接矩阵int vexnum,arcnum;			//图的当前点数和边数
}AMGraph;

图的定义和术语

Graph = (Vertex,Edge)
G = (V,E)
V:Vertex 顶点,描述:顶点数据有有穷非空集合。
E:Edge 边,描述:边的有空集合。

🚲有向图:每条边都是有方向的

🚲无向图:每条边都是无方向的

🚲无向完全图:其中任意一点,都和其余所有点相连接(无方向)。

V1 和 V2、V3、V4 相互连接
V2 和 V1、V3、V4 相互连接
V3 和 V1、V2、V4 相互连接
V4 和 V1、V2、V3 相互连接

n 个顶点, n ( n − 1 ) / 2 条边 \color{orange}n个顶点,n(n-1)/2条边 n个顶点,n(n1)/2条边
解释:(n-1):求单个顶点的最大边数
如果有A、B、C三个顶点
则A 的最大边数:A 和 B连,A 和 C 连。 = 2条(因为A无法和自己相连,所以单个顶点的最大边数 = 所有顶点数-自身 = n-1

解释:n(n-1):求所有顶点的最大边数之和
(n-1)为单个顶点的最大边数,乘以n 就为所有顶点的最大边数之和

解释:n(n-1)/2:边数
已经求出 n(n-1) 为所有顶点的最大边数之和,假设有三个顶点A、B、C。
A的最大边数为A 和 B连,A 和 C 连
B的最大边数为B 和 A连,B 和 C 连
可以看出来吗?第一次A和B连,第二次B和A连,其实重复了,边只有一个,但计算了两次。/2 的目的是为了消除所有单条边计算了两次的问题

🚲有向完全图:其中任意一点,都和其余所有点相连接(有方向)。

注意:有向图是每两个点有两条边相连,而不是一条双箭头的边
n 个顶点, n ( n − 1 ) 条边 \color{orange}n个顶点,n(n-1)条边 n个顶点,n(n1)条边
V1 和 V2、V3、V4 相互连接
V2 和 V1、V3、V4 相互连接
V3 和 V1、V2、V4 相互连接
V4 和 V1、V2、V3 相互连接

n 个顶点, n ( n − 1 ) 条边 \color{orange}n个顶点,n(n-1)条边 n个顶点,n(n1)条边
解释:因为每两个顶点有两条边,把 /2去掉就行了。

🚲连通图

含义:所有的顶点都可以通过直接或间接的方式,到达任意一个顶点
无向图的连通图

有向图的连通图

🚲非连通图

含义:有一个或大于一个的顶点,无法到达所有顶点,或无法被所有顶点到达任意一个顶点。
可以看到从V2无法到达任何一个顶点。
有向图的非连通图

无向图的非连通图

🛴有向图

稀疏图 \color{orange}稀疏图 稀疏图: 有很少边或弧的图(e < n l o g n n_{log}n nlogn)。
稠密图 \color{orange}稠密图 稠密图:有较多边或弧的图。
网 \color{orange} 网 :        边/弧带权的图。
邻接 \color{orange}邻接 邻接:有边/弧相连的两个顶点之间的关系。
            存在( V i , V j V_i,V_j Vi,Vj),则称 V i V_i Vi V j V_j Vj互为邻接点;
            存在< V i , V j V_i,V_j Vi,Vj>,则称 V i V_i Vi邻接到 V j V_j Vj V j V_j Vj邻接于 V i V_i Vi
关联(依附) \color{orange}关联(依附) 关联(依附):边/弧与顶点之间的关系。
          存在( V i , V j V_i,V_j Vi,Vj)/< V i , V j V_i,V_j Vi,Vj>,则称该边/弧关联于 V i 和 V j V_i和V_j ViVj
顶点的度 \color{orange}顶点的度 顶点的度:与该顶点相关联的边的数量,记为TD(V)
有向图的入度 \color{orange}有向图的入度 有向图的入度:其它顶点指向该顶点的边数。
有向图的出度 \color{orange}有向图的出度 有向图的出度:该顶点指向其它顶点的边数。
有向图 \color{orange}有向图 有向图中,顶点的度为该顶点的 入度 \color{orange}入度 入度 出度 \color{orange}出度 出度的和。

路径 \color{orange}路径 路径:连接的边构成的顶点序列。
路径长度 \color{orange}路径长度 路径长度:路径上 (边或弧的数目/权值之和)。
回路 ( 环 ) \color{orange}回路(环) 回路():第一个顶点和最后一个顶点相同的路径。
简单路径 \color{orange}简单路径 简单路径:除路径起点和终点可以相同,其余顶点均不相同的路径。
简单路径 ( 简单环 ) \color{orange}简单路径(简单环) 简单路径(简单环):除路径起点和终点相同外,其余顶点均不相同的路径。

权 \color{orange}权 :图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。
网 \color{orange}网 :带权的图称为网。
子图 \color{orange}子图 子图:设有两个图G=(V,{E})、G1=(V1,{E1})、若 V 1 ∈ V , E 1 ∈ E , 则称 G 1 是 G 的子图。 V1\in V,E1 \in E,则称G1是G的子图。 V1V,E1E,则称G1G的子图。
极大连通子图 \color{orange}极大连通子图 极大连通子图:该子图是G的连通子图,将G图分成多个子图,其中一个子图每个顶点都可以连接,若将一个子图中的顶点移入到该子图,则该子图的这个顶点无法与任意一个顶点相互连通,则称该子图为极大连通子图。
连通分量(强连通分量) \color{orange}连通分量(强连通分量) 连通分量(强连通分量):无向图G的极大连通子图称为G的连通分量。
极小连通子图 \color{orange}极小连通子图 极小连通子图:该子图是G的连通子图,在该子图中删除任何一条边,则该子图不再连通。
生成树 \color{orange}生成树 生成树:包含无向图G所有顶点的极小连通子图。
生成森林 \color{orange}生成森林 生成森林:对非连通图,由各个连通分量的生成树的集合。

图的操作

CreateGraph(*G,V,VR)

初始条件: V是图的顶点集,VR是图中弧的集合。
操作结果:按V和VR的定义 构造图 G \color{orange}构造图G 构造图G

DFSTraverse(G)

初始条件: 图G存在。
操作结果:对图进行 深度优先遍历 \color{orange}深度优先遍历 深度优先遍历

BFSTraverse(G)

初始条件: 图G存在。
操作结果:对图进行 广度优先遍历 \color{orange}广度优先遍历 广度优先遍历

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

燃料电池混合电源的能量管理系统

这个例子显示了燃料电池混合电源的能量管理系统。 这个例子展示了燃料电池混合电源的能量管理系统。 电路描述 本文给出了基于燃料电池的多电动飞机应急动力系统的仿真模型。随着MEA中起落架和飞控系统的电气化程度的提高&#xff0c;常规应急电源系统(冲压式空气涡轮或空气驱…

01:Linux的基本命令

Linux的基本命令 1、常识1.1、Linux的隐藏文件1.2、绝对路径与相对路径 2、基本命令2.1、ls2.2、cd2.3、pwd / mkdir / mv / touch / cp / rm / cat / rmdir2.4、ln2.5、man2.6、apt-get 本教程是使用的是Ubuntu14.04版本。 1、常识 1.1、Linux的隐藏文件 在Linux中&#xf…

【ROS中Cjson文件的作用】

在ROS (Robot Operating System) 中&#xff0c;.json 文件通常用于存储配置信息、数据序列化或者在某些情况下用于网络通信和数据交换。JSON&#xff08;JavaScript Object Notation&#xff09;是一种轻量级的数据交换格式&#xff0c;易于人阅读和编写&#xff0c;同时也易于…

【WebGIS干货分享】Webgis 面试题-浙江中海达

1、Cesium 中有几种拾取坐标的方式&#xff0c;分别介绍 Cesium 是一个用于创建 3D 地球和地理空间应用的 JavaScript 库。在 Cesium 中&#xff0c;你可以使用不同的方式来拾取坐标&#xff0c;以便与地球或地图上的对象进行交 互。以下是 Cesium 中几种常见的拾取坐标的方式…

深入理解C++中的锁

目录 1.基本互斥锁&#xff08;std::mutex&#xff09; 2.递归互斥锁&#xff08;std::recursive_mutex&#xff09; 3.带超时机制的互斥锁&#xff08;std::timed_mutex&#xff09; 4.带超时机制的递归互斥锁&#xff08;std::recursive_timed_mutex&#xff09; 5.共享…

[论文阅读笔记33] Matching Anything by Segmenting Anything (CVPR2024 highlight)

这篇文章借助SAM模型强大的泛化性&#xff0c;在任意域上进行任意的多目标跟踪&#xff0c;而无需任何额外的标注。 其核心思想就是在训练的过程中&#xff0c;利用strong augmentation对一张图片进行变换&#xff0c;然后用SAM分割出其中的对象&#xff0c;因此可以找到一组图…

网络爬虫基础知识

文章目录 网络爬虫基础知识爬虫的定义爬虫的工作流程常用技术和工具爬虫的应用1. 抓取天气信息2. 抓取新闻标题3. 抓取股票价格4. 抓取商品价格5. 抓取博客文章标题 网络爬虫基础知识 爬虫的定义 网络爬虫&#xff08;Web Crawler 或 Spider&#xff09;是一种自动化程序&…

《企业实战分享 · 常用运维中间件》

&#x1f4e2; 大家好&#xff0c;我是 【战神刘玉栋】&#xff0c;有10多年的研发经验&#xff0c;致力于前后端技术栈的知识沉淀和传播。 &#x1f497; &#x1f33b; 近期刚转战 CSDN&#xff0c;会严格把控文章质量&#xff0c;绝不滥竽充数&#xff0c;如需交流&#xff…

HUAWEI MPLS 静态配置和动态LDP配置

MPLS(Multi-Protocol Label Switching&#xff0c;多协议标签交换技术)技术的出现&#xff0c;极大地推动了互联网的发展和应用。例如&#xff1a;利用MPLS技术&#xff0c;可以有效而灵活地部署VPN(Virtual Private Network&#xff0c;虚拟专用网)&#xff0c;TE(Traffic Eng…

a-range-picker 国际化不生效

1、问题&#xff1a;按照官方 添加后是这样的 周和月没有翻译 1-1官方配置如下图 1-2效果&#xff1a; 2、import locale from "ant-design-vue/es/date-picker/locale/zh_CN"; 打印出locale是这样的 这个文件翻译文件中没有相关翻译 3、解决&#xff1a; 简单粗…

【实战场景】记一次UAT jvm故障排查经历

【实战场景】记一次UAT jvm故障排查经历 开篇词&#xff1a;干货篇&#xff1a;1.查看系统资源使用情况2.将十进制进程号转成十六进制3.使用jstack工具监视进程的垃圾回收情况4.输出指定线程的堆内存信息5.观察日志6.本地环境复现 总结篇&#xff1a;我是杰叔叔&#xff0c;一名…

Objective-C使用块枚举的细节

对元素类型的要求 在 Objective-C 中&#xff0c;NSArray 只能存储对象类型&#xff0c;而不能直接存储基本类型&#xff08;例如 int&#xff09;。但是&#xff0c;可以将基本类型封装在 NSNumber 等对象中&#xff0c;然后将这些对象存储在 NSArray 中。这样&#xff0c;en…

H6922 便携移动储能升压恒压方案 2.8-40V耐压 7.5A大电流应用芯片IC

H6922芯片是一款便携移动储能升压恒压控制驱动芯片&#xff0c;满足2.8-40V宽输入电压范围的升压恒压电源应用而设计。下面我将基于您提供的信息&#xff0c;对H6922的特性和典型应用进行更详细的解释。 产品特性详解 宽输入电压&#xff1a;H6922支持2.8-40V的宽输入电压范围…

【Windows】Visual Studio Installer下载缓慢解决办法

【Windows】Visual Studio Installer下载缓慢解决办法 1.背景2.分析3.结果 1.背景 使用visual studio在线安装包进行IDE安装&#xff0c;发现下载几乎停滞&#xff0c;网速几乎为零。 经过排查并不是因为实际网络带宽导致。 这里涉及DNS知识&#xff1b; DNS&#xff08;Dom…

SCI丨5分期刊,JCR一区

SCI&#xff0c;5分&#xff0c;JCR Q1&#xff0c;中科大类3小类2区 1 基于复杂网络与xxx能源汽车节能数值分析 2 基于热能损失优化的xxx与性能管理 3 基于xxxLCA技术的绿色制造工艺优化研究 4 基于xxx入侵检测技术的物联网智能制造监控系统设计 6 基于物联网技术xxx电力系…

BMP280 环境传感器

型号简介 BMP280是博世&#xff08;bosch-sensortec&#xff09;的一款气压传感器&#xff0c;特别适用于移动应用。其小尺寸和低功耗使其能够应用于电池供电的设备&#xff0c;如手机、GPS 模块或手表。基于博世久经考验的压阻式压力传感器技术&#xff0c;具有高精度和线性度…

Elasticsearch备份数据到本地,并导入到新的服务 es 服务中

文章目录 使用elasticsearch-dump工具备份安装node.js(二进制安装)解压设置环境变量安装elasticsearch-dump docker安装使用ES备份文件到本地 使用elasticsearch-dump工具备份 这个工具备份时间比较长 安装node.js(二进制安装) wget https://nodejs.org/dist/v16.18.0/node-…

SpringBoot: Eureka入门

1. IP列表 公司发展到一定的规模之后&#xff0c;应用拆分是无可避免的。假设我们有2个服务(服务A、服务B)&#xff0c;如果服务A要调用服务B&#xff0c;我们能怎么做呢&#xff1f;最简单的方法是让服务A配置服务B的所有节点的IP&#xff0c;在服务A内部做负载均衡调用服务B…

基于FPGA的DDS信号发生器

前言 此处仅为基于Vivado实现DDS信号发生器的仿真实现&#xff0c;Vivado的安装请看下面的文章&#xff0c;这里我只是安装了一个标准版本&#xff0c;只要能够仿真波形即可。 FPGA开发Vivado安装教程_vivado安装 csdn-CSDN博客 DDS原理 DDS技术是一种通过数字计算生成波形…

图解 Kafka 架构

写在前面 Kafka 是一个可横向扩展&#xff0c;高可靠的实时消息中间件&#xff0c;常用于服务解耦、流量削峰。 好像是 LinkedIn 团队开发的&#xff0c;后面捐赠给apache基金会了。 kafka 总体架构图 Producer&#xff1a;生产者&#xff0c;消息的产生者&#xff0c;是消息的…