跳转至

图论基础

图是怎么存的?

直接存边

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

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

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

邻接矩阵

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

如果边有权值,也可以直接用 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,也称为 ,是起点和终点相同的路径。

简单回路

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

连通

两个点连通

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

图连通

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

可达

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

强连通

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

弱连通

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

子图

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

生成子图

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

导出子图

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

边导出子图

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

连通子图

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

连通分量

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

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

稀疏图

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

稠密图

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

完全图

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

路径的长度

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

最短路径

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

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


评论