发布于 ,更新于 

图论基础

图论是嗜血分支1,相应的,图论基础并没有什么太多需要思考的东西,只有一堆该死的概念等着记,有如绳之以法抽象了

基本概念

由顶点(点)(Vertex)的集合和边(Edge)的集合组成,记为 \(\mathbb{G} = (\mathbb{V}+\mathbb{E})\)
点的集合用 \(\mathbb{V(G)}\) 表示,点用 \(u,v\) 等符号表示
顶点的数量称为图的“阶”,用 \(n\) 表示
边的集合用 \(\mathbb{E(G)}\) 表示,边用 \(e\) 等符号表示
边的个数称为图的“边数” 感觉说了和没说一样,用 \(m\) 表示 分量:一个图的子图(涉及:强连通分量

图的种类

\(u\)\(v\) 的无向边: \((u,v)\)
\(u\)\(v\) 的有向边:\(\langle u,v \rangle\)

有向图:图的所有边都是有向边
无向图:图的所有边都是无向边
完全图:每个点都与其他所有顶点连接;对于有向图来说,任意顶点 \(u,v\) 都有边 \(\langle u,v \rangle \langle v,u \rangle\)
稀疏图/稠密图:边少/多的图
平凡图:一个点的图
零图:没有边的图

对于顶点 \(v\) 来说
入度 \(ID(v)\):以 \(v\) 为终点的边的个数
出度 \(OD(v)\):以 \(v\) 为起点的边的个数
\(D(v)\) = 入度 + 出度

度为奇数的点为奇点,度为偶数的顶点为偶点

于是可得:对于图 \(\mathbb{G}\) 中所有顶点的度=边数的两倍
以及推论:一个图中的奇点数量为偶数

简短证明: 1. 每条边一定贡献一个出度一个入度共两个度
2. 度一定是偶数所以奇点的数量为偶数(奇\(\times\)\(=\)偶)

存图

无向图可以看作有向图但是两个点之间互相有一条有向边,所以只需要考虑有向图存图

邻接矩阵

基本思想是存两个点之间的边权(不连接即为 0 或 -1)

比如当前图有四个点,则开数组 g[5][5],初始化为 0。

1234
10000
20000
30000
40000

然后 1 到 2,3 到 1 有一条有向边,边权为 1,则修改 g[1][2] g[3][1] 为 1

1234
10100
20000
31000
40000

非常容易理解,缺点也显而易见,如果有 \(114514\) 个点但是只有 \(1\) 条边,那就需要开 \(114514^2\) 的空间但是只有一个位置有数据,显然造成了巨大的浪费(空间早就炸了)
因此需要寻找一个只存边的存图方案,从而诞生邻接表

邻接表

考虑一件事情,对于一个图来说,有两个元素:点、边,而点的相关要素可以通过数组来以点为单位存储。
考虑存边:边的要素有三个,即起点、终点以及边权。考虑把边看作一个对象存储。

链式前向星

用链表实现的邻接表

先说链表,顾名思义,链状链接的列表,在这里我们把同一个起点边存到一个链表里。

开一个结构体存链的每一个元素

1
2
3
4
5
struct edge {
int data;
int to;
edge *nex;
};

显然,把链表每一个部分连接起来的东西就是指针 nexnex 指向当前元素的下一个元素的地址。 当然,如果开一个数组存储所有的元素,地址可以改为存储下标,即 nex 可以是一个整数,存储下一个元素在数组里的下标。


  1. 数学,来自 GrainRain谷神↩︎