图论基础

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

基本概念

图

由顶点（点）（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。

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

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

邻接表

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

链式前向星

用链表实现的邻接表

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

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

1
2
3
4
5

struct edge {
    int data;
    int to;
    edge *nex;
};

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