跳转至

图论基础

图是怎么存的?

直接存边

什么意思呢?我们开一个数组,数组里每个元素是图的一条边。

这样做有个缺点,每次想要知道两个点之间是否有连边(或者说一条边是否存在),都需要在数组里进行一番查找。而且如果没有对边事先排序的话,就不能使用二分查找的方法( O(\log n) ),而是每次只能按顺序找( O(n) ),成本较高。

什么时候会用到这个方法呢?最简单的一个例子是使用 Kruskal 算法求 最小生成树 的时候。

邻接矩阵

邻接矩阵的英文名是 adjacency matrix。它的形式是 bool adj[n][n],这里面 n 是节点个数, adj[i][j] 表示 i j 之间是否有边。

如果边有权值,也可以直接用 int adj[n][n],直接把边权存进去。

它的优点是可以在 O(1) 时间内得到一条边是否存在,缺点是需要占用 O(n^2) 的空间。对于一个稀疏的图(边相对于点数的平方比较少)来说,用邻接矩阵来存的话,成本偏高。

邻接表

邻接表英文名是 adjacency list。它的形式是 vector adj[n],用 adj[i] 存以 i 为起点的边。

vector 无法科学地删除,所以常用 list 实现。

它的特点是可以用来按顺序访问一个结点的出边(或者入边)。

前向星

为什么它搜不到英文名呢?因为是中国玩家乱搞出来的。

首先介绍一下链式前向星,本质上是用单向链表实现的邻接表。

形式上是一个结构体:struct edge {edge *pre, int to;} *head[N], edge[M]

这个结构广泛出现于算法竞赛选手的代码中,编写简洁而且对于大多数题目效率足够高。

其中 head[i] 用来存以 i 为起点的边,edge 数组是边表。

那么什么是前向星呢?事先把 edge 数组排个序即可。这里可以使用 基数排序 做到 O(m)

一些跟图有关的定义

路径

path,是指一个边的序列,其中的边首尾相连。

简单路径

simple path,是每条边只经过了一次的路径。

回路

cycle,也称为 ,是起点和终点相同的路径。

简单回路

图的定点序列中,除了起点和终点相同外,其余顶点不重复的回路。

连通

两个点连通

无向图中点 u v 连通是指存在一条 u v 的路径。

图连通

如果无向图 G 中任意两个节点连通,称其为是连通的。

可达

有向图中点 u v 可达是指存在一条 u v 的路径。

强连通

有向图 G 强连通是指, G 中任意两个节点连通。

弱连通

有向图 G 弱连通是指, G 中的所有边替换为无向边后, G 为连通图。

子图

选取一个节点的子集和边的子集构成的图。

生成子图

选取的子图的节点和原图一样。

导出子图

选取一个节点的子集,再选取这些节点相关联的边的集合构成的图。

边导出子图

选取一个边的子集,再选取这些边相关联的节点的集合,构成的图。

连通子图

(一个无向图的)连通的子图。

连通分量

(一个无向图的)极大的连通子图。

【注】:极大是指添加任何节点或者边后都不再满足。

稀疏图

m = \Theta(n) 的图,或者指 m 相对较小的图。

稠密图

m = \Theta(n^2) 的图,或者指 m 相对较大的图。

完全图

m = \frac{n(n-1)}{2} 的简单无向图。

路径的长度

一般来说,路径的长度在数值上等于路径的边数,或者如果边是带权的,则是路径的边权和。

最短路径

两个节点之间,长度最小的路径。

【注】:不一定存在,不一定唯一。


评论