训练计划
什么是图?
图是一种复杂的非线性结构。
在线性结构中,数据元素之间满足唯一的线性关系,每个数据元素(除第一个和最后一个外)只有一个直接前趋和一个直接后继;
在树形结构中,数据元素之间有着明显的层次关系,并且每个数据元素只与上一层中的一个元素(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 图的存储