[C++数据结构之看懂就这一篇]图(上)


📚博客主页：Zhui_Yi_
🔍：上期回顾：JAVA面向对象（上）
❤️感谢大家点赞👍🏻收藏⭐评论✍🏻，您的三连就是我持续更新的动力❤️
🎇追当今朝天骄，忆顾往昔豪杰。

9796ba31acb84a41a33779fb39bfb109.gif

一、图的概念

1.图的定义

图：Graph=(V,E)

V：顶点(数据元素)的有穷非空集合；
E：边的有穷集合

2.图的分类

图又分为有向图和无向图。
无向图是：每条边都是无方向的
image.png
有向图是：每条边都是有方向的
image.png
其中开始的位置我们称为弧尾，结束的位置我们称为弧头。

3.图的术语

子图

设有两个图G=（V，{E}）、G1=（V1，{E1}），若V1包含于 V，E1 包含于 E，则称 G1是G的子图。

例:(b)、© 是 (a) 的子图
image.png

完全图

任意两个点都有一条边相连

也分为有向和无向。
image.png
而对于无向完全图来说，如果有n个顶点，那么有多少条边嘞？

对于第n个点来说，它连接了n-1条边
对于第n-1个点来说，它连接了n-1-1条边
对于第n-2个点来说，它连接了n-1-1-1条边
…
那么即：image.png

而对于有向完全图来说，如果有n个顶点，那么有多少条边嘞？
它是无向完全图的2倍，即：n(n-1)

稀疏图

有很少边或弧的图。

稠密图

有较多边或弧的图。

权与网

图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。带权的图称为网。

4.边

邻接

有边/弧相连的两个顶点之间的关系 存在(vi, vj)，则称vi和vj互为邻接点；存在<vi, vj>，则称vi邻接到vj，vj邻接于vi。
vi称为始点或弧尾，vj称为终点或弧头。

关联(依附)

边/弧与顶点之间的关系。存在(vi, vj)/ <vi, vj>， 则称该边/弧关联于vi和vj

对于边<0，1>,称顶点0“邻接到”顶点1,顶点1“邻接于”顶点0，弧<0，1>与顶点0和1“相关联”。

5.点

顶点的度

与该顶点相关联的边的数目，记为TD(v)

在有向图中, 顶点的度等于该顶点的入度与出度之和。
顶点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v) 顶点 v 的出度是以 v 为始点的有向边的条数, 记作OD(v)

那么当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状？
答：是树！而且是一棵有向树！
关于结点度的重要结论：

若一个图(有向/无向)中有n个顶点和e条边，且每个顶点的度为di (0≤i≤n-1 )则image.png
即图中所有顶点的度之和等于边数的两倍。

6.路径

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

image.png

7.连通图

图G=( V, E)中，若对任意两个顶点v、u，无向图从v到u都是连通的，则称G是连通图;有向图从v到u和从u到v都存在路径则称G是强连通图。

image.png

连通分量

无向图G的极大连通子图称为G的连通分量。
极大连通子图意思是:该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通。

极小连通图

极小连通子图:该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通。

其他概念

生成树：包含无向图G 所有顶点的极小连通子图。
生成森林：对非连通图，由各个连通分量的生成树的集合。

image.png

结论

如果G1是一个有n个顶点的连通无向图，则G1最多有多少条边?最少有多少条边?

为完全无向图时边最多→n(n-1)/2，
为树时边数最少→n-1

如果G2是一个有n个顶点的强连通有向图，则G2最多有多少条边?最少有多少条边?

为完全有向图时边最多 →n(n-1)
为树时边数最少(有弧指向根 →)n

二、图的存储

引入

在前面我们学过的一些知识中，线性表有唯一的前驱和后继，树中有唯一的双亲和多个后继，但在图里，一个点可能有好多前趋和后继。

图中任意两个顶点之间可能存在联系，因此不能以数据元素在内存中的物理位置表示元素之间的关系(内存中物理位置是线性的)

此时还是有两种存储方式：顺序存储结构和链式存储结构

其中我们重点掌握：邻接矩阵和邻接表

数组（邻接矩阵）表示法

我们首先考虑一下，我们会在图中存储哪些信息嘞？
图的定义中包含了顶点和边，所以我们就要存储这两个信息，即：

建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。

image.png
设图 A = (V, E) 有 n 个顶点，则图的邻接矩阵是一个二维数组 A.Edge[n][n]，如果图不带权，定义为：image.png

无向图的邻接矩阵表示法

image.png
如图，则我们要建立5*5大小的数组，即：
image.png
那么我们该如何表示它们之间的关系呢？
有关系的话为1，无关系的话为0，即：
image.png
我们再看一下这个图片，有什么规律吗？
关于对角线对称，这很容易理解，在无向图中，一个顶点与另一个顶点有关系的话，那么这个顶点既有出度，也有入度。
那么既然是对称矩阵了，我们是不是可以压缩存储。
那么除了这个，我们还能知道些什么呢？
每个顶点的行或列相加即为这个顶点的度。
特别：完全图的邻接矩阵中，对角元素为0，其余1。
空间复杂度即为：O（n2）。

有向图的邻接矩阵表示法

image.png
我们可以建立如下矩阵：
image.png
植入关系后：
image.png
注意一下：

在有向图的邻接矩阵中， 第i行含义：以结点vi为尾的弧(即出度边）； 第i列含义：以结点vi为头的弧(即入度边）。

而规律如下：

分析1：有向图的邻接矩阵可能是不对称的。
分析2：顶点的出度=第i行元素之和
顶点的入度=第i列元素之和
顶点的度=第i行元素之和+第i列元素之和

网（即有权图）的邻接矩阵表示法

image.png
无穷大为自己定义。
image.png
对于这个网而言，我们该如何存储？
image.png
如下图：
image.png

邻接矩阵的存储表示（以网为例）

首先我们先设置两个值

#define MaxInt 32767                    	//表示极大值，即∞
#define MVNum 100                       	//最大顶点数

然后呢，我们要存储点和边，即我们需要定义两个数组，一个点集，一个边集，在此之前，我们先定义一下其他的：

typedef char VerTexType;              	//假设顶点的数据类型为字符型 
typedef int ArcType;                  	//假设边的权值类型为整型

然后我们再定义结构体：

typedef struct{ 
  VerTexType vexs[MVNum];            		//顶点表 
  ArcType arcs[MVNum][MVNum];      		//邻接矩阵 
  int vexnum,arcnum;                		//图的当前点数和边数 
}AMGraph;

image.png
对于这个图，你认为改存哪些信息？
四个顶点，五条边，以及五个权值。
即
image.png
即整个算法思想为：

（1）输入总顶点数和总边数。
（2）依次输入点的信息存入顶点表中。
（3）初始化邻接矩阵，使每个权值初始化为极大值。
（4）构造邻接矩阵。

我们此时定义：

AMGraph &G

故我们要先输入总点数和总边数：

 cin>>G.vexnum>>G.arcnum; 	//输入总顶点数，总边数

然后再输入顶点的信息：

  for(i = 0; i<G.vexnum; ++i)    
      cin>>G.vexs[i];  	//依次输入点的信息

然后再初始化邻接矩阵，使权值为最大值（若无权值，则将其初始化为0）：

 for(i = 0; i<G.vexnum;++i) //初始化邻接矩阵，边的权值均置为极大值
       for(j = 0; j<G.vexnum;++j)   
         G.arcs[i][j] = MaxInt;  //有权值
         //G.arcs[i][j] = 0;//无权值

即
image.png
最后再构造邻接矩阵：
那么此时就会有一个问题，我们将500赋值给A到B的这条边？
那么我们是不是需要先找到A和B，然后再将A和B转化成相对应的位置信息，那么我们该如何找到A和B呢？
故我们需要从点集中进行遍历，返回A和B的位置对应的下标：

 int LocateVex(MGraph G,VertexType u)
 {//存在则返回u在顶点表中的下标;否则返回-1
   int i;
   for(i=0;i<G.vexnum;++i)
     if(u==G.vexs[i])
       return i;
   return -1;
 }

故构造邻接矩阵：

 for(k = 0; k<G.arcnum;++k){                     //构造邻接矩阵 
      cin>>v1>>v2>>w;   //无权值的时候，这步骤不需要                              //输入一条边依附的顶点及权值 
      i = LocateVex(G, v1);  j = LocateVex(G, v2);  //确定v1和v2在G中的位置
      G.arcs[i][j] = w; //边<v1, v2>的权值置为w 
     //G.arcs[i][j] =1；//无权值的时候
      G.arcs[j][i] = G.arcs[i][j];              //置<v1, v2>的对称边<v2, v1>的权值为w 
   }

完整代码如下：

bool CreateUDN(AMGraph &G){ 
    //采用邻接矩阵表示法，创建无向网G 
    cin>>G.vexnum>>G.arcnum; 	//输入总顶点数，总边数 
    for(i = 0; i<G.vexnum; ++i)    
      cin>>G.vexs[i];                        	//依次输入点的信息 
    for(i = 0; i<G.vexnum;++i) 	//初始化邻接矩阵，边的权值均置为极大值
       for(j = 0; j<G.vexnum;++j)   
         G.arcs[i][j] = MaxInt;   
    for(k = 0; k<G.arcnum;++k){                     //构造邻接矩阵 
      cin>>v1>>v2>>w;                                 //输入一条边依附的顶点及权值 
      i = LocateVex(G, v1);  j = LocateVex(G, v2);  //确定v1和v2在G中的位置
      G.arcs[i][j] = w; //边<v1, v2>的权值置为w 
      G.arcs[j][i] = G.arcs[i][j];              //置<v1, v2>的对称边<v2, v1>的权值为w 
   }//for 
   return true; 
}

总结

优点：容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边、找顶点的邻接点等等。
缺点：n个顶点需要n*n个单元存储边;空间效率为O(n2)。 对稀疏图而言尤其浪费空间。

邻接表（链式）表示法

既然是链式，那么我们可以和单链表结合在一起：

存储顶点信息：

每个单链表有一个头结点（设为2个域），存vi信息；
每个单链表的头结点另外用顺序存储结构存储。

顺序存储，是这样吗：

A
B
C
D

顶点是存下来了，那么它指向的那个顶点嘞？
我们可以在搞一个域，用来存储第一个指向的结点即：
image.png
那么存储完点了，该如何存储边呢？

存储边的信息

每个顶点vi 建立一个单链表，把与vi有关联的边的信息链接起来，每个结点设为3个域。

image.png
image.png

存储表示

image.png
我们首先先看一下这个图片，我们是应该先存储黄色部分，还是蓝色部分？
当然是黄色部分，因为我们蓝色部分要指向黄色部分，如果黄色部分未声明的话，那么肯定会悬空。
即：

typedef struct ArcNode{                		//边结点 
int adjvex;                          		//该边所指向的顶点的位置 
struct ArcNode * nextarc;          	//指向下一条边的指针 
OtherInfo info;                      	              //和边相关的信息 
}ArcNode;

然后我们就要声明蓝色部分的：
蓝色部分包含什么？
一个结点和一个指针：

typedef struct VNode{ 
VerTexType data;                        	//顶点信息 
ArcNode * firstarc;                     	//指向第一条依附该顶点的边的指针 
}VNode;               						//AdjList表示邻接表类型

此时是不是声明完了？
当然没有啊，我们还没存储顶点数和边数呢！

typedef struct{ 
    VNode v[MVNum];                 		//邻接表 
    int vexnum, arcnum;              		//图的当前顶点数和边数 
}ALGraph;

整体代码如下：

#define MVNum 100                        	//最大顶点数 
typedef struct ArcNode{                		//边结点 
    int adjvex;                          		//该边所指向的顶点的位置 
    struct ArcNode * nextarc;          	//指向下一条边的指针 
    OtherInfo info;                      	              //和边相关的信息 
}ArcNode; 
typedef struct VNode{ 
    VerTexType data;                        	//顶点信息 
    ArcNode * firstarc;                     	//指向第一条依附该顶点的边的指针 
}VNode；              							//AdjList表示邻接表类型 
typedef struct{ 
    VNode v[MVNum];                 		//邻接表 
    int vexnum, arcnum;              		//图的当前顶点数和边数 
}ALGraph;

无向图的邻接表表示

image.png
我们首先看这个图片，有几个顶点？
5个，我们把它们存到顺序表中：
image.png
然后我们再根据每一个结点与其他结点相连来扩充：
image.png
我们看上表，能发现什么？邻接表是否唯一？
当然不唯一，你不知道每个结点后的顺序排列如何。比如，v1后面可以改为：1，3
空间效率为O（n+2e)其中e为边数。

有向图的邻接表表示

image.png
空间效率为O（n+e)

出度OD(Vi)=单链出边表中链接的结点数
入度ID(Vi)=整个链表中邻接点域为Vi的结点个数
度:TD(Vi)=OD+ID

网的邻接表表示

对于带权值的网，可以在边表定义中增加一个数据域存储权值。
image.png

总结

由于后面的知识有点遗忘，而且我太久没写东西了，就先发着一部分，抱歉，各位！！！

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

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

相关文章

C++面向对象程序设计 - 输入输出流进一步研究

C++面向对象程序设计 - 输入输出流进一步研究

在C中&#xff0c;输入输出流&#xff08;I/O&#xff09;是一个强大的特性&#xff0c;它允许程序与各种输入/输出设备&#xff08;如键盘、显示器、文件等&#xff09;进行交互。C标准库中的<iostream>头文件定义了基本的输入输出流类&#xff0c;如std::cin&#xff0…
阅读更多...
从河流到空气，BL340工控机助力全面环保监测网络构建

从河流到空气，BL340工控机助力全面环保监测网络构建

在环保监测领域&#xff0c;智能化、高效率的监测手段正逐步成为守护绿水青山的新常态。其中&#xff0c;ARMxy工业计算机BL340凭借其强大的处理能力、高度的灵活性以及广泛的兼容性&#xff0c;在水质监测站、空气质量检测、噪音污染监控等多个环保应用场景中脱颖而出&#xf…
阅读更多...
Apache ShardingSphere实战与核心源码剖析

Apache ShardingSphere实战与核心源码剖析

Apache ShardingSphere实战与核心源码剖析 1.数据库架构演变与分库分表介绍 1.1 海量数据存储问题及解决方案 如今随着互联网的发展，数据的量级也是成指数的增长，从GB到TB到PB。对数据的各种操作也是愈加的困难，传统的关系性数据库已经无法满足快速查询与插入数据的需求。…
阅读更多...
常见的api：BigDecima

常见的api：BigDecima

一.计算中的小数 float和double占有的位置是有限的 二.BigDecima的作用 1.用于小数的精确计算 2.用来表示很大的小数 三.使用(传入小数) BigDecimal b1 new BigDecimal(0.01);BigDecimal b2 new BigDecimal(0.09);System.out.println(b1);System.out.println(b2); 不精确&…
阅读更多...
creo学习一

creo学习一

设置好当前配置后&#xff0c;导出config配置文件&#xff0c;并覆盖掉此路径下的旧文件&#xff0c;使得新配置永久生效&#xff0c;这样每次打开软件都是新配置的设置&#xff1a; 系统颜色的导出&#xff1a; 打开版本的问题&#xff1a; 不能有弱尺寸&#xff1a; 注意&a…
阅读更多...
搭建vauditdemo靶场mysql为NO问题

搭建vauditdemo靶场mysql为NO问题

一、问题 在搭建vauditdemo时&#xff0c;遇到如下显示问题&#xff1a; mysql版本检测为NO 二、解决 查找该方面问题时&#xff0c;并没有找到解决方法 然后换mysql版本换了五六个也没有解决问题 问了AI后给的答复有一条为将mysql改为mysqli 修改保存后解决问题 步骤如…
阅读更多...
280 基于matlab的摇号系统GUI界面仿真MATLAB程序

280 基于matlab的摇号系统GUI界面仿真MATLAB程序

基于matlab的摇号系统GUI界面仿真MATLAB程序&#xff0c;输入总数量及摇号需求&#xff0c;进行随机性摇号&#xff0c;并对摇取的号码进行双重随机性数据检测&#xff0c;确定是否符合要求。程序已调通&#xff0c;可直接运行。 280 GUI人机交互 摇号系统GUI界面仿真 - 小红书…
阅读更多...
RocketMq详解：二、SpringBoot集成RocketMq

RocketMq详解：二、SpringBoot集成RocketMq

在上一章中我们对Rocket的基础知识、特性以及四大核心组件进行了详细的介绍&#xff0c;本章带着大家一起去在项目中具体的进行应用&#xff0c;并设计将其作为一个工具包只提供消息的分发服务和业务模块进行解耦 在进行本章的学习之前&#xff0c;需要确保你的可以正常启动和…
阅读更多...
cnvd_2015_07557-redis未授权访问rce漏洞复现-vulfocus复现

cnvd_2015_07557-redis未授权访问rce漏洞复现-vulfocus复现

1.复现环境与工具 环境是在vulfocus上面 工具&#xff1a;GitHub - vulhub/redis-rogue-getshell: redis 4.x/5.x master/slave getshell module 参考攻击使用方式与原理&#xff1a;https://vulhub.org/#/environments/redis/4-unacc/ 2.复现 需要一个外网的服务器做&…
阅读更多...
Docker Swarm持久化

Docker Swarm持久化

Docker Swarm持久化 1 简介 Docker Swarm持久化有bind、volume和NFS三种方式&#xff0c;bind和volume两种方式适合挂载单个宿主机&#xff0c;不适合集群&#xff1b;NFS适合集群服务&#xff0c;但需要安装NFS系统。 注意&#xff1a;Docker Swarm需要先安装集群。 由Doc…
阅读更多...
AI作画工具介绍

AI作画工具介绍

目录 1.概述 2.Stable Diffusion 2.1.诞生背景 2.2.版本历史 2.3.优点 2.4.缺点 2.5.应用场景 2.6.未来展望 3.Midjourney 3.1.诞生背景 3.2.版本历史 3.3.优点 3.4.缺点 3.5.应用场景 3.6.未来展望 4.总结 1.概述 AI作画工具是一种运用人工智能技术&#xff…
阅读更多...
JAVA网络编程，反射及注解知识总结

JAVA网络编程，反射及注解知识总结

文章目录 网络编程软件架构三要素IP端口号协议UDP协议发送数据接收数据三种通信方式 TCP协议客户端服务器端三次握手四次挥手 反射获取字节码文件获取构造方法获取成员变量获取成员方法反射的作用 动态代理注解作用格式使用位置注解的原理常见注解元注解自定义注解解析注解 网络…
阅读更多...
【OC】类与对象

【OC】类与对象

类与对象 定义类接口部分定义成员变量方法说明实现部分 对象的产生与使用对象与指针self关键字避免重复创建 id类型方法详解方法的所属性形参个数可变的方法 成员变量成员变量及其运行机制多个实例中内存示意图模拟类变量单例模式 类是面向对象的重要内容&#xff0c;我们可以把…
阅读更多...
【问题解决】adb remount 失败或刷机无法连接设备（KaiOS）

【问题解决】adb remount 失败或刷机无法连接设备（KaiOS）

问题描述 1、设备无法adb remount成功&#xff0c; 2、通过fastboot无法识别设备&#xff0c;一直卡住 3、已经识别到9008端口&#xff0c;但是设备与刷机工具connect fail&#xff0c;甚至软件crash 解决方案 1、安装高通驱动工具&#xff1a;QDLoder HS-USB Driver QDLoade…
阅读更多...
【工作必备知识】Linux磁盘I/O故障排查分析定位 iostat 介绍

【工作必备知识】Linux磁盘I/O故障排查分析定位 iostat 介绍

【工作必备知识】Linux磁盘I/O故障排查分析定位 iostat 介绍 大家好&#xff0c;我是秋意零。 前言&#xff1a;今天&#xff0c;介绍Linux磁盘I/O故障排查时&#xff0c;必备命令iostat。该命令是监视系统I/O设备使用负载&#xff0c;它可以实时监视IO设备&#xff0c;从而帮…
阅读更多...
Python数据分析II

Python数据分析II

目录 1.HS-排序返回前n行 2.HS-相关性 3.缺失值处理 4.时间 5.时间索引 6.分组聚合 7.离散分箱 8.Concat关联(索引关联) 9.Merge关联(字段关联) 10.join合并(左字段,右索引) 11.行列转置及透视表 12.数据可视化-面向过程 13.数据可视化-面向对象 14.快速生成柱状…
阅读更多...
10秒钟docker 安装Acunetix

10秒钟docker 安装Acunetix

1、拉取镜像&#xff1a; 2、查看镜像&#xff1a; [rootdns-server ~]# docker images REPOSITORY TAG IMAGE ID CREATED SIZE quay.io/hiepnv/acunetix latest f8415551b8f4 2 months ago 1.98GB 3、运行镜像&#xff1a; …
阅读更多...
msfconsole利用Windows server2008cve-2019-0708漏洞入侵

msfconsole利用Windows server2008cve-2019-0708漏洞入侵

一、环境搭建 Windows系列cve-2019-0708漏洞存在于Windows系统的Remote Desktop Services&#xff08;远程桌面服务&#xff09;&#xff08;端口3389&#xff09;中&#xff0c;未经身份验证的攻击者可以通过发送特殊构造的数据包触发漏洞&#xff0c;可能导致远程无需用户验…
阅读更多...
已解决Error || IndexError: index 3 is out of bounds for axis 0 with size 3

已解决Error || IndexError: index 3 is out of bounds for axis 0 with size 3

已解决Error || IndexError: index 3 is out of bounds for axis 0 with size 3 原创作者&#xff1a; 猫头虎 作者微信号&#xff1a; Libin9iOak 作者公众号&#xff1a; 猫头虎技术团队 更新日期&#xff1a; 2024年6月6日 博主猫头虎的技术世界 &#x1f31f; 欢迎来…
阅读更多...
Android安全开发之 Provider 组件安全

Android安全开发之 Provider 组件安全

Android系统中的Content Provider组件是一种用于在不同应用之间共享数据的机制。它提供了一种安全、可控的方式&#xff0c;允许应用访问其他应用的数据。然而&#xff0c;如果Provider组件的安全措施没有得到妥善实现&#xff0c;则可能会导致严重的安全漏洞&#xff0c;例如数…
阅读更多...
最新文章

Copyright @ 2022~2023