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

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

news 来源：原创 2024/6/27 0:46:45


📚博客主页：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在顶点表中的下标;否则返回-1int 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

总结

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

相关文章：

  • 【C++初阶学习】第十三弹——优先级队列及容器适配器
  • Dubbo动态服务下线
  • 整数反转（leetcode）
  • 中国自研的AI算力基建和服务的发展
  • [数据集][目标检测]厨房积水检测数据集VOC+YOLO格式88张2类别
  • Redis Key过期监听配置
  • nginx优化与防盗链【☆☆☆】
  • fastapi学习前置知识点
  • 前端工程化工具系列（十一）—— Babel(v7.24)：JavaScript编译器
  • 多线程详解
  • Redis到底支不支持事务？
  • MySQL 存储函数及调用
  • C语言 | Leetcode C语言题解之第142题环形链表II
  • Position定位
  • 深度学习之文本分类模型-基于transformer
  • 《网管员必读——网络组建》（第2版）电子课件下载
  • Docker 1.12实践：Docker Service、Stack与分布式应用捆绑包
  • ES6语法详解(一)
  • jquery cookie
  • PHP 小技巧
  • Vue 动态创建 component
  • 反思总结然后整装待发
  • 简单易用的leetcode开发测试工具（npm）
  • 如何解决微信端直接跳WAP端
  • 腾讯视频格式如何转换成mp4 将下载的qlv文件转换成mp4的方法
  • 腾讯优测优分享 | Android碎片化问题小结——关于闪光灯的那些事儿
  • 为物联网而生：高性能时间序列数据库HiTSDB商业化首发！
  • 阿里云ACE认证学习知识点梳理
  • 阿里云API、SDK和CLI应用实践方案
  • #Spring-boot高级
  • $.ajax,axios,fetch三种ajax请求的区别
  • (1) caustics\
  • （3）医疗图像处理：MRI磁共振成像-快速采集--(杨正汉）
  • (a /b)*c的值
  • (C11) 泛型表达式
  • (c语言版)滑动窗口 给定一个字符串，只包含字母和数字，按要求找出字符串中的最长（连续）子串的长度
  • （没学懂，待填坑）【动态规划】数位动态规划
  • (轉貼) 蒼井そら挑戰筋肉擂台 (Misc)
  • .NET CORE Aws S3 使用
  • .NET企业级应用架构设计系列之结尾篇
  • .NET上SQLite的连接
  • ?.的用法
  • @angular/cli项目构建--Dynamic.Form
  • @cacheable 是否缓存成功_Spring Cache缓存注解
  • @KafkaListener注解详解（一）| 常用参数详解
  • @synthesize和@dynamic分别有什么作用？
  • [ C++ ] STL_vector -- 迭代器失效问题
  • [20171106]配置客户端连接注意.txt
  • [20180224]expdp query 写法问题.txt
  • [20190401]关于semtimedop函数调用.txt
  • [383] 赎金信 js
  • [Android学习笔记]ScrollView的使用
  • [Angular 基础] - 表单：响应式表单
  • [Angularjs]ng-select和ng-options
  • [boost]使用boost::function和boost::bind产生的down机一例