【数据结构与算法】图的存储

🔥 本文由 程序喵正在路上 原创，CSDN首发！
💖 系列专栏：数据结构与算法
🌠 首发时间：2022年11月13日
🦋 欢迎关注🖱点赞👍收藏🌟留言🐾
🌟 一以贯之的努力 不得懈怠的人生

邻接矩阵法（顺序存储）

图中点和点之间是否有连接，我们可以用一个表来表示，其中 “1” 表示两点之间有边，反之

上图很容易用代码表示出来

#define MaxVertexNum 100						//顶点数目的最大值
typedef struct{
	char Vex[MaxVertexNum];						//顶点表
	int Edge[MaxVertexNum][MaxVertexNum];		//邻接矩阵，边表
	int vexnum, arcnum;							//图的当前顶点数和边数/弧数
} MGraph;
1
2
3
4
5
6

顶点的数组中我们可以存储更复杂的信息，比如一个结构体

结点数为 $n$ 的图 $G=(V,E)$ 的邻接矩阵 $A$ 是 $n\times n$ 的，将 $G$ 的顶点编号为 $v_1,v_2,\dots ,v_n$， 则

KaTeX parse error: No such environment: align* at position 8: \begin{̲a̲l̲i̲g̲n̲*̲}̲ \begin{split} …

在这种情况下，我们怎么求顶点的度、入度和出度呢？

• 对于无向图，第 $i$ 个结点的度 $=$ 第 $i$ 行（或第 $i$ 列）的非零元素个数
• 对于有向图，第 $i$ 个结点的出度 $=$ 第 $i$ 行的非零元素个数，第 $i$ 个结点的入度 $=$ 第 $i$ 列的非零元素个数，，第 $i$ 个结点的度 $=$ 第 $i$ 行、第 $i$ 列的非零元素个数之和

邻接矩阵法求顶点的度 / 出度 / 入度的时间复杂度均为 $O(|V|)$

邻接矩阵法存储带权图（网）

#define MaxVertexNum 100						//顶点数目的最大值
#define INFINITY 最大的int值						//宏定义常量 “无穷”
typedef char VertexType;						//顶点的数据类型
typedef int EdgeType;							//带权图中边上权值的数据类型
typedef struct{
	VertexType Vex[MaxVertexNum];				//顶点
	EdgeType Edge[MaxVertexNum][MaxVertexNum];	//边的权
	int vexnum, arcnum;							//图的当前顶点数和弧数
} MGraph;
1
2
3
4
5
6
7
8
9

邻接矩阵法的性能分析

空间复杂度：$O(|V|)$ —— 只和顶点数相关，和实际的边数无关，邻接矩阵法采用数组顺序存储的形式，适合用于存储稠密图

无向图的邻接矩阵是对称矩阵，我们可以压缩存储，也就是只存储上三角区或者下三角区

邻接矩阵法的性质

设图 $G$ 的邻接矩阵为 $A$（矩阵元素为 $0/1$），则 $A^n$ 的元素 $A^n[i][j]$ 等于由顶点 $i$ 到顶点 $j$ 的长度为 $n$ 的路径的数目

假设 $A$ 如下表所示

现在要计算 $A^2[1][4],A^2[2][2]$，该怎么做呢？
$$\begin{gathered} A^2[1][4]=a_{11}\times a_{14}+a_{12}\times a_{24}+a_{13}\times a_{34}+a_{14}\times a_{44}=1 \\ {A}^2[2][2]=a_{21}\times a_{12}+a_{22}\times a_{22}+a_{23}\times a_{32}+a_{24}\times a_{42}=3 \end{gathered}$$
其中 $a_{11}$ 表示矩阵的第 $1$ 行第 $1$ 个元素，其他依此类推

我们画出 $A^2$ 的表，如下

可以发现，我们计算出来的值就是这个表中对应位置的值

如果让你计算 $A^3[1][4]$ 呢？

邻接表法（顺序+链式存储）

// “边/弧”
typedef struct ArcNode{
	int adjvex;						//边/弧指向哪个结点
	struct ArcNode *next;			//指向下一条弧的指针
	InfoType info;					//边权值（没有可不加）
}ArcNode;

// “顶点”
typedef struct VNode{
	VertexType data;			//顶点信息
	ArcNode *first;				//第一条边/弧
}VNode, AdjList[MaxVertexNum];

//用邻接表存储的图
typedef struct{
	AdjList vertices;
	int vexnum, arcnum;
}ALGraph;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

当然，有向图也可以用邻接表法来表示

空间复杂度分析

对于无向图，由于每一条边都会有一个指向的结点占空间，而且是双向的，比如 $A$ 和 $B$ 之间有一条边，那么
$A$ 到 $B$ 这条边就会有一个指向 $B$ 的结点，同理 $B$ 到 $A$ 这条边就会有一个指向 $A$ 的结点，由于边结点的数量是 $2|E|$ ，所以整体的空间复杂度为 $O(|V|+2|E|)$

对于有向图，由于每条边都是有方向的，所以只会有一个指向结点，整体的空间复杂度即为 $O(|V|+|E|)$

度、入度和出度

那么，下面我们思考一下怎么求顶点的度、入度和出度呢？

• 对于无向图，我们只要遍历边结点的链表就能求出对应顶点的度
• 对于有向图，通过遍历边结点的链表我们就能求出对应顶点的出度；但是要得到某个顶点的入度，就很麻烦了，我们需要遍历所有顶点相应的边结点的链表，这也是邻接表法的一个缺点

邻接矩阵和邻接表的对比

图的邻接表表示方式并不唯一，与一个顶点有关系的边的顺序是可以颠倒排列的；但是对于前面的邻接矩阵来说，只要确定了顶点编号，那图的邻接矩阵就是唯一的

十字链表

我们需要定义两个结构：弧结点和顶点结点

空间复杂度为：$O(|V|+|E|)$

如何找到指定顶点的所有出边？ —— 顺着绿色线路找
如何找到指定顶点的所有入边？ —— 顺着橙色线路找

注意：十字链表只用于存储有向图

邻接多重表

空间复杂度为：$O(|V|+|E|)$

删除边、删除节点等操作很方便

注意：邻接多重表只用于存储无向图

总结