2.图的存储及基本操作

6.2.5图的基本操作

邻接矩阵法

所谓邻接矩阵存储,是指用一个一维数组存储图中顶点的信息,用一个二维数组存储图中边的信息(即各顶点之间的邻接关系),存储顶点之间邻接关系的二维数组称为邻接短阵。

代码未仔细校对，且没有优化排版 (@2023-08-17)

#define MaxVertexNum 100 //顶点数目的最大值
typedef char VertexType; //顶点的数据类型
typedef int EdgeType; //带权图中边上权值的数据类型
typedef struct{
	VertexType Vex [MaxVertexNum];//顶点表
	EdgeType Edge [MaxVertexNum] [MaxVertexNum];//邻接矩阵，边表
	int vexnum, arcnum; //图的当前顶点数和弧数
}MGraph;

注意

在简单应用中,可直接用二维数组作为图的邻接矩阵(顶点信息等均可省略)。
当邻接矩阵的元素仅表示相应边是否存在时,Edgetype 可采用值为口和1的枚举类型。
无向图的邻接矩阵是对称矩阵,对规模特大的邻接矩阵可采用压缩存储。
邻接矩阵表示法的空间复杂度为 $O(n^2)$ ,其中n为图的顶点数 $\mid V\mid$

特点

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

邻接表法

所谓邻接表, 是指对图 ${G}$ 中的每个顶点 ${v_{i}}$ 建立一个单链表, 第 ${i}$ 个单链表中的结点表示依附于顶点 ${v_{i}}$ 的边 (对于有向图则是以顶点 ${v_{i}}$ 为尾的弧), 这个单链表就称为顶点 ${v_{i}}$ 的边表 (对于有向图则称为出边表)。边表的头指针和顶点的数据信息采用顺序存储 (称为顶点表), 所以在邻接表中存在两种结点: 顶点表结点和边表结点, 如图所示。

代码只是单纯ocr，并没有校对 (@2023-08-17)

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

若G为无向图，则所需的存储空间为 $O(|V|+2|E|)$ ：若G为有向图，则所需的存储空间为 $O(|V|+|E|)_{\circ}$ 。前者的倍数2是由于无向图中，每条边在邻接表中出现了两次。
对于稀疏图，采用邻接表表示将极大地节省存储空间。
在邻接表中，给定一顶点，能很容易地找出它的所有邻边，因为只需要读取它的邻接表。
在邻接矩阵中，相同的操作则需要扫描一行，花费的时间为 $O(n)$ 。但是，若要确定给定的两个顶点间是否存在边，则在邻接矩阵中可以立刻查到，而在邻接表中则需要在相应结点对应的边表中查找另一结点，效率较低。
在有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表中的结点个数；但求其顶点的入度则需要遍历全部的邻接表。因此，也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。当然，这实际上与邻接表存储方式是类似的。
=图的邻接表表示并不唯一，因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。

十字链表

6.2.3%2B6.2.4十字链表、邻接多重表

00:00

十字链表是有向图的一种链式存储结构。在十字链表中,对应于有向图中的每条弧有一个结点,对应于每个顶点也有一个结点。这些结点的结构如下所示。
图的十字链表表示是不唯一的,但一个十字链表表示确定一个图。

弧结点

tailvex	headvex	hlink	tlink	(info)

顶点结点

data	firstin	firstout

空间复杂度: $O(\mid V\mid+\mid E\mid)$

邻接多重表

邻接多重表是无向图的另一种链式存储结构。
在邻接表中,容易求得顶点和边的各种信息,但在邻接表中求两个顶点之间是否存在边而对边执行删除等操作时,需要分别在两个顶点的边表中遍历,效率较低。
与十字链表类似,在邻接多重表中,每条边用一个结点表示,其结构如下所示。
| ivex | ilink | jvex | jlink | (info) |
| ---- | ----- | ---- | ----- | ------ |

每个顶点也用一个结点表示,它由如下所示的两个域组成

data	firstedge

其中,data 域存放该顶点的相关信息,firstedge 域指向第一条依附于该顶点的边

对无向图而言,其邻接多重表和邻接表的差别仅在于, 同一条边在邻接表中用两个结点表示,而在邻接多重表中只有一个结点。

对比

后两个方法只需要理解特性就行，代码实现比较复杂，考研中不会让你手写代码

图的基本操作

6.2.5图的基本操作

00:00

Adjacent $(\mathrm{G}, \mathrm{x}, \mathrm{y})$ : 判断图 G 是否存在边 $\langle x, y\rangle$ 或 $(x, y)$ 。
Neighbors $(G, x)$ : 列出图 $G$ 中与结点 $x$ 邻接的边。
InsertVertex $(\mathrm{G}, \mathrm{x})$ : 在图 $G$ 中插入顶点 $x_{0}$ 。
DeleteVertex $(\mathrm{G}, \mathrm{x})$ : 从图 $G$ 中删除顶点 $x$ 。
AddEdge $(\mathrm{G}, \mathrm{x}, \mathrm{y})$ : 若无向边 $(x, y)$ 或有向边 $\langle x, y>$ 不存在, 则向图 $G$ 中添加该边。
RemoveEdge $(\mathrm{G}, \mathrm{x}, \mathrm{y})$ : 若无向边 $(x, y)$ 或有向边 $\langle x, y\rangle$ 存在, 则从图 $G$ 中删除该边。
FirstNeighbor $(\mathrm{G}, \mathrm{x})$ : 求图 $G$ 中顶点 $x$ 的第一个邻接点, 若有则返回顶点号。若 $x$ 没有邻接点或图中不存在 $x$ , 则返回 -1 。
NextNeighbor $(\mathrm{G}, \mathrm{x}, \mathrm{y})$ : 假设图 $G$ 中顶点 $y$ 是顶点 $x$ 的一个邻接点, 返回除 $y$ 外顶点 $x$ 的下一个邻接点的顶点号, 若 $y$ 是 $x$ 的最后一个邻接点, 则返回 - 1 。
Get_edge_value $(\mathrm{G}, \mathrm{x}, \mathrm{y})$ : 获取图 $G$ 中边 $(x, y)$ 或 $\langle x, y\rangle$ 对应的权值。
Set_edge_value $(\mathrm{G}, \mathrm{x}, \mathrm{y}, \mathrm{v})$ : 设置图 $G$ 中边 $(x, y)$ 或 $\langle x, y>$ 对应的权值为 $v$ 。

结论了解即可, 证明方法请参考离散数学教材。 ↩︎

2.图的存储及基本操作

# 邻接矩阵法

# 特点

# 邻接表法

# 十字链表

# 邻接多重表

# 图的基本操作

邻接矩阵法

特点

邻接表法

十字链表

邻接多重表

图的基本操作