图的基本概念|存储-EW帮帮网

微信交流群：https://732903.hlcode.cn/?id=NK1fWUR

图的基本概念

图的定义

图G由顶点集V和边集E组成，记为G=（V，E)
其中V(G)表示图G中顶点的有限非空集；E（G)表示图G中顶点之间的关系（边）集合。
若V={ $v_{1},v_{2},\dots,v_{n}$ )，则用 $∣ V ∣$ 表示图G中顶点的个数
E={ $\in V, v\in V$ )，则用 $∣ E ∣$ 表示图G中边的条数

图的顶点集V一定非空，但边集E可以为空，此时图中只有顶点而没有边。

有向图
若E是有向边（也称弧）的有限集合，则图G为有向图。
弧是顶点的有序对，记为<v,w>，其中v,w是顶点，v称为弧尾，w称为弧头，<v,w>称为从v到w的弧，也称v邻接到w。

$G_{1} = (V_{1},E_{1})$
$V_{1}=\left\{ 1,2,3 \right\}$
$E_{1}=\left\{ <1,2>,<2,1>,<2,3> \right\}$
2. 无向图
若E是无向边（简称边）的有限集合，则图G为无向图。
边是顶点的无序对，记为（v,w）或(w,v)。可以说w和v互为邻接点。
边（v,w)依附于w和v，或称边（v,w)和v,w相关联。
![[Pasted image 20241215213701.png]]

$G_{2} = (V_{2},E_{2})$
$V_{2}=\left\{ 1,2,3,4 \right\}$
$E_{2}=\left\{ (1,2),(1,3),(1,4),(2,3),(2,4),(3,4) \right\}$
3. 简单图
一个图G若满足：
1. 不存在重复边；
2. 不存在顶点到自身的边，则称图G为简单图。
若图G中某两个顶点之间的边数大于1条，又允许顶点通过一条边和自身关联，则称图G为多重图。。
4. 完全图
对于无向图， $∣ E ∣$ 的取值范围为 $0$ 到 $\frac{n(n-1)}{2}$ ，有 $\frac{n(n-1)}{2}$ 条边的无向图称为完全图，在完全图中任意两个顶点之间都存在边。
对于有向图，E的取值范围为 $0$ 到 $n (n - 1)$ ，有 $n (n - 1)$ 条弧的有向图称为有向完全图，在有向完全图中任意两个顶点之间都存在方向相反的两条弧。
![[Pasted image 20241215220438.png]]

子图
设有两个图G=（V,E)和G’=（V’,E’)，若V’是V的子集，且E’是E的子集，则称G’是G的子集。
若有满足V(G‘)=V(G)的子图G’，则称其为G的生成子图。
连通、连通图和连通分量
在无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。
若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。
无向图中的极大连通子图称为连通分量，图G4有3个连通分量。
假设一个图有n个顶点，若边数小于n-1，则此图必是非连通图；
强连通图，强连通分量
在有向图中，若有一对顶点v和w，从v到w和从w到v之间都有路径，则称这两个顶点是强连通的。
若图中任意一对顶点都是强连通的，则称此图为强连通图。
有向图中的极大强连通子图称为有向图的强连通分量
生成树，生成森林
连通图的生成树是包含图中全部顶点的一个极小连通子图。
若图中顶点数为n，则它的生成树含有n-1条边。
包含图中全部顶点的极小连通子图，只有生成树满足这个极小条件，对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。
在非连通图中，连通分量的生成树构成了非连通图的生成森林。
顶点的度，入度和出度
在无向图中，顶点v的度是指依附于顶点v的边的条数，记为TD(v)。
无向图的全部顶点的度之和等于边数的2倍，因为每条边和两个顶点相关联。
在有向图中，顶点v的度分为入度和出度，入度是以顶点v为终点的有向边的数目，记为 ID(v)；
而出度是以顶点v为起点的有向边的数目，记为OD(v)。
顶点v的度等于其入度与出度之和，即TD(v)=ID(v)+OD(v)。
有向图的全部顶点的入度之和与出度之和相等，并且等于边数，这是因为每条有向边都有一个起点和终点。
边的权和网
在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
这种边上带有权值的图称为带权图，也称网。
稠密图、稀疏图
边数很少的图称为稀疏图，反之称为稠密图。
稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。
一般当图G满足 $|E|<|V|\log|V|$ 时，可以将G视为稀疏图。
路径，路径长度和回路
顶点 $v_{p}$ 到顶点 $v_{q}$ 之间的一条路径是指顶点序列 $v_{p},v_{i1},v_{i 2},\dots ,v_{in},v_{q}$ ，当然关联的边也可理解为路径的构成要素。
路径上的边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。
若一个图有n个顶点，且有大于n-1条边，则此图一定有环。
简单路径，简单回路
在路径序列中，顶点不重复出现的路径称为简单路径。
除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
距离
从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。
若从u到v根本不存在路径，则记该距离为无穷
有向树
一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树。

图的存储及基本操作

邻接矩阵法

所谓邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中
边的信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵。
顶点数为n的图G=(V,E)的邻接矩阵A是 $\times n$ 的，将G的顶点编号为 $v_{1},v_{2},\dots,v_{n}$ ，则
$A[i][j]=\left\{\begin{matrix} 1,\qquad (v_{i},v_{j})或<v_{i},v_{j}>是E(G)中的边 \\ 0,\qquad (v_{i},v_{j})或<v_{i},v_{j}>不是E(G)中的边 \end{matrix}\right.$
对带权图而言，若顶点v和v之间有边相连，则邻接矩阵中对应项存放着该边对应的权值，若顶点 $v_{i}$ 和 $v_{j}$ 不相连，则通常用0或 $\infty$ 来代表这两个顶点之间不存在边：
$KaTeX parse error: Can't use function '$' in math mode at position 32: …\begin{matrix} $̲w_{ij}$,\qquad …$

邻接矩阵存储结构定义

#define MaxVertexNum 100                        // 顶点数目的最大值
typedef char VertexType;                        // 顶点对应的数据类型
typedef int EdgeType;                           // 边对应的数据类型
typedef struct
{
	VertexType vex[MaxVertexNum];               // 顶点表
	EdgeType edge[MaxVertexNum][MaxVertexNum];  // 邻接矩阵，边表
	int vexnum, arcnum;                         // 图的当前顶点数和边数
}MGraph;

在这里插入图片描述

图的邻接矩阵存储表示法具有以下特点：

无向图的邻接矩阵一定是一个对称矩阵（并且唯一)。因此，在实际存储邻接矩阵时只需
存储上（或下）三角矩阵的元素。
对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非元素）的个数正好是顶点i的度TD( $v_{i}$ )。
对于有向图，邻接矩阵的第i行非零元素（或非 $\infty$ 元素）的个数正好是顶点i的出度 OD( $v_{i}$ )；第i列非零元素（或非 $\infty$ 元素）的个数正好是顶点i的入度ID( $v_{i}$ )。
用邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图
中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。
稠密图（即边数较多的图）适合采用邻接矩阵的存储表示。
设图G的邻接矩阵为A， $A^{n}$ 的元素 $A^{n}[i][j]$ 等于由顶点i到顶点j的长度为n的路径的数目。

邻接表法

当一个图为稀疏图时，使用邻接矩阵法显然会浪费大量的存储空间，而图的邻接表法结合了顺序存储和链式存储方法，大大减少了这种不必要的浪费。
所谓邻接表，是指对图G中的每个顶点 $v_{i}$ 建立一个单链表，第i个单链表中的结点表示依附于顶点 $v_{i}$ 的边（对于有向图则是以顶点 $v_{i}$ 为尾的弧），这个单链表就称为顶点 $v_{i}$ 的边表（对于有向图则称为出边表）。边表的头指针和顶点的数据信息采用顺序存储，称为顶点表，所以在邻接表中存在两种结点：顶点表结点和边表结点
![[Pasted image 20241216140134.png]]

顶点表结点由两个域组成：顶点域（data）存储顶点 $v_{i}$ 的相关信息，边表头指针域（firstarc）指向第一条边的边表结点。
边表结点至少由两个域组成：邻接点域（adjvex）存储与头结点顶点 $v_{i}$ 邻接的顶点编号，指针域（nextarc）指向下一条边的边表结点。
![[Pasted image 20241216140503.png]]

![[Pasted image 20241216140510.png]]

邻接表存储结构定义

#define MaxVertexNum 100         // 图中顶点数目的最大值
typedef char VertexType;         // 顶点类型
typedef int EdgeType;            // 边的权值的类型
// 边/弧
typedef struct ArcNode           // 边表节点
{
	int adjvex;                  // 该弧所指向的顶点的位置
	struct ArcNode* nextarc;     // 指向下一条弧的指针
	// InfoType info;            // 网的边权值
}ArcNode;
// 顶点
typedef struct VNode             // 顶点表节点
{
	VertexType data;             // 顶点信息
	ArcNode* firstarc;           // 指向第一条依附该顶点的弧的指针
}VNode, AdjList[MaxVertexNum];
// 用邻接表存储的图
typedef struct
{
	AdjList vertices;            // 邻接表
	int vexnum, arcnum;          // 图的顶点数和弧数
}ALGraph;                        // ALGraph是以邻接表存储的图类型

![[Pasted image 20241216144502.png]]

若G为无向图，则所需的存储空间为 $O (∣ V ∣ + 2∣ E ∣)$ ：若G为有向图，则所需的存储空间为 $O (∣ V ∣ + ∣ E ∣ ）$ 。前者的倍数2是因为在无向图中，每条边在邻接表中出现了两次。
对于稀疏图（即边数较少的图），采用邻接表表示将极大地节省存储空间。
在邻接表中，给定一个顶点，能很容易地找出它的所有邻边，因为只需要读取它的邻接表。在邻接矩阵中，相同的操作则需要扫描一行，花费的时间为O(n)。但是，若要确定给定的两个顶点间是否存在边，则在邻接矩阵中可以立刻查到，而在邻接表中则需要在相应结点对应的边表中查找另一结点，效率较低。
在无向图的邻接表中，求某个顶点的度只需计算其邻接表中的边表结点个数。在有向图的邻接表中，求某个顶点的出度只需计算其邻接表中的边表结点个数；但求某个顶点x的入度则需遍历全部的邻接表，统计邻接点（adjvex）域为x的边表结点个数。
图的邻接表表示并不唯一，因为在每个顶点对应的边表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。

图的基本概念|存储