图的存储方式

训练计划

什么是图?

图是一种复杂的非线性结构。

在线性结构中,数据元素之间满足唯一的线性关系,每个数据元素(除第一个和最后一个外)只有一个直接前趋和一个直接后继;

在树形结构中,数据元素之间有着明显的层次关系,并且每个数据元素只与上一层中的一个元素(parent node)及下一层的多个元素(孩子节点)相关;

而在图形结构中,节点之间的关系是任意的,图中任意两个数据元素之间都有可能相关。

图G由两个集合V(顶点Vertex)和E(边Edge)组成,定义为G=(V,E)

图论 (Graph theory) 是数学的一个分支,图是图论的主要研究对象。

图 (Graph) 是由若干给定的顶点及连接两顶点的边所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物,连接两顶点的边则用于表示两个事物间具有这种关系。


图的相关概念(了解)

无向边

若顶点 U 到 V 之间的边没有方向,这条边就叫做无向边(Edge)

无向图

如果图中任意两个顶点之间的边都是无向边,则称该图为无项图(Undirected graphs)。

有向边

若从顶点 U 到 V 的边有方向,则称这条边为有向边,也称为弧 (Arc)。

有向图

如果图中任意两个顶点之间的边都是有向边,这个图就是有向图。

简单图

在图中,若不存在顶点到其自身的边,且同一条边不重复出现,这样的图就是简单图。

有向完全图

在有向图中,如果任意两点之间都存在方向互为相反的两条弧,这个图就是有向完全图。
n个顶点的有向完全图有 n(n-1)/2条边。


图的存储结构

直接存边

使用一个结构体数组来存边,数组中的每个元素都包含一条边的起点与终点(带边权的图还包含边权)。(或者使用多个数组分别存起点,终点和边权。)

复杂度:
查询是否存在某条边 O(m)。
遍历一个点的所有出边 O(m)。
遍历整张图 O(n*m)。
空间复杂度:O(m)。

应用:
由于直接存边的遍历效率低下,一般不用于遍历图。
在 Kruskal 算法 中,由于需要将边按边权排序,需要直接存边。
在有的题目中,需要多次建图(如建一遍原图,建一遍反图),此时既可以使用多个其它数据结构来同时存储多张图,也可以将边直接存下来,需要重新建图时利用直接存下的边来建图。

邻接矩阵(常用):

参考代码:https://jhcloud.top/jpaste/?f6ff309c469025a1#cmMrbW/ZzwIiEYfXMt/x9+fKPNs6AZAHBcdWQT3eKpc=
邻接矩阵使用两个数组存储图。

顶点数组:一维数组 VERTEX,存放顶点的数据信息。如 VERTEX = [v1, v2, v3]

邻接矩阵:二维数组 A,下标表示顶点,元素表示顶点之间的关系。对于 A[i][j] 而言,存储的元素代表 VERTEX 中顶点 i 与顶点 j 间的边的信息。

一般而言,在无权图的邻接矩阵中,如果顶点间有边时,存储元素为 1,无边存放 0。如无向图 G1 和有向图 G2 的表示方法如下,它们的边都没有权重:

而对于网络(带权图)来说,邻接矩阵元素为边上的权值 w_{ij},当无边时,可以用无穷大 ∞ 表示。

邻接矩阵的存储方式有如下特点:
1、无向图的邻接矩阵一定是对称矩阵。按压缩存储的思想,我们可以只用存储上三角或下三角元素。
2、无向图的第 i 行或第 i 列非零元素(或非 ∞ 元素)个数正好是第 i 个顶点的度。
3、有向图的第 i 行或第 i 列非零元素(或非 ∞ 元素)个数正好是第 i 个顶点的出度或入度。

空间复杂度 O(n^2)
时间复杂度
查询是否存在某条边:O(1)。
遍历一个点的所有出边:O(N)。
遍历整张图:O(n^2)。
空间复杂度:O(n^2)。

应用:
邻接矩阵只适用于没有重边(或重边可以忽略)的情况。
其最显著的优点是可以 O(1) 查询一条边是否存在。
由于邻接矩阵在稀疏图上效率很低(尤其是在点数较多的图上,空间无法承受),所以一般只会在稠密图上使用邻接矩阵。

邻接表:

邻接表使用顺序存储与链式存储相结合。

数组:存放顶点的数据信息。
链表:存放边的信息。

邻接表首先由一个数组,存放了所有的顶点结点,以每一个顶点结点作为头结点,又有 n 个链表,分别存放每个顶点依附的边。
同样是上面的 G1、G2 两张图,使用邻接表存储如下:

边结点里的序号指代的是顶点在顶点数组中间的索引。
对于网络来讲,边结点还需存储边的权重。

空间复杂度:O(m)
时间复杂度:
查询是否存在 u 到 v 的边:O(u的出边数)。
遍历点 u 的所有出边:O(u的出边数) 。
遍历整张图:O(n+m)。
空间复杂度:O(m)。

应用:
存各种图都很适合,除非有特殊需求(如需要快速查询一条边是否存在,且点数较少,可以使用邻接矩阵)。

尤其适用于需要对一个点的所有出边进行排序的场合。

十字链表(了解)

https://blog.csdn.net/wwh578867817/article/details/44748557

链式前向星(常用)

邻接表的一种实现:
参考代码:https://jhcloud.top/jpaste/?5c9ce06f50ad1aad#d8KIoeP4eGYaD5u6h8ETaYll6ngPYc1rWHxZL+MAd0c=


练手题目:

直接存边1:图的基本存储的基本方式二(提示:本题题面有误,m<=5e4 && q<=5e4, 时间复杂度 m*q 可过)

直接存边2:图的基本存储的基本方式三

邻接矩阵:图的基本存储的基本方式一

邻接矩阵/邻接表:图的基本存储的基本方式四(提示:建议大家使用邻接表(包含前向星)练习)


参考资料

8.2 图的存储方式
数据结构与算法:图和图算法(一)
数据结构学习笔记之图
数据结构–图的存储方式
oi-wiki 图的存储

发表评论

电子邮件地址不会被公开。 必填项已用*标注