基本概念
图论相关定义在不同教材中往往会有所不同，遇到的时候需根据上下文加以判断。
本文将介绍部分常用概念，更多图论相关知识请自行了解。
图：
定义：
图是一个二元组 $G=(V(G),E(G))$。其中 $V(G)$ 是非空集，称为点集，对于 $V$ 中的每个元素，我们称之为顶点或节点，简称点；$E(G)$ 为 $V(G)$ 各节点之间的边的集合，称为边集。
常简化用 $G=(V,E)$ 表示图。
无向图：
若 $G$ 为无向图，则 $E$ 中每一个元素为一个无序二元组 $(u,v)$，称作无向边。$u,v$ 称作端点。
有向图：
若 G 为有向图，则 E 中每一个元素为一个有序二元组 $(u,v)$，有时也称作 $u\rightarrow v$。$u$ 称作起点，$v$ 称作终点。称 $u$ 是 $v$ 的直接前驱，$v$ 是 $u$ 的直接后继。
有权图：
若图为有权图，则用 $(u,v,w)$ 描述一条边。
简单图：
若一个图中没有自环和重边，则被称为简单图。
自环：
对 $E$ 中的边 $e=(u,v)$，若 $u=v$，则 $e$ 被称作一个自环。
重边：
若 $E$ 中存在两个完全相同的元素 $e_1=e_2$，则它们被称作一组重边。
addition:
无向图中，$(u,v)$ 和 $(v,u)$ 算作重边；有向图中，$(u,v)$ 和 $(v,u)$ 不算作重边。
图的度：
无向图：
与一个顶点相关的边的条数称作该点的度。
有向图：
入度：以一个顶点为终点的边数。
出度：以一个顶点为起点的边数。
addition：
无向图的度在欧拉回路/欧拉路径中有特殊应用。
有向图的度在拓扑排序中有特殊应用。
图的路径：
途径：
途径是连接一连串顶点的边的序列，可以为有限或无限长度。形式化地说，一条有限途径 $w$ 是一个边的序列 $e_1,e_2,…,e_k$，使得存在一个顶点序列 $v_0,v_1,…,v_k$ 满足 $e_i=(v_{i-1},v_i)$。通常来说，边的数量 $k$ 被称作这题途径的长度（如果边是带权的，长度通常指途径上的边权之和）
迹：
对于一条途径 $w$，若 $e_1,e_2,…,e_k$ 两两互不相同，则称 $w$ 是一条迹。
路径：
路径又称简单路径。
从一个点出发不经过相同点的边序列称为路径（简单路径）。
子图：
对于一张图 $G=(V,E)$，若存在另一张图 $H=(V’,E’)$ 满足 $V’\subseteq V$ 且 $E’\subseteq E$，则称 $H$ 是 $G$ 的子图，记作 $H\subseteq G$。
图的连通性：
无向图：
对于一张无向图 $G=(V,E)$，对于 $u,v\in V$，若存在一条路径使得从 $u$ 出发可以到 $v$，则称 $u$ 和 $v$ 是连通的。
若无向图 $G=(V,E)$ 满足其中任意两个顶点均连通，则称 $G$ 是连通图，$G$ 具有连通性。
若 $H$ 是 $G$ 是一个连通子图，$H\subsetneq F\subsetneq G$ 且 $F$ 为连通图，则 $H$ 是 $G$ 的一个连通块/连通分量（极大连通子图）
有向图：
对于一张无向图 $G=(V,E)$，对于 $u,v\in V$，若存在一条路径使得从 $u$ 出发可以到 $v$，则称 $u$ 可达 $v$。
树：
定义：
任意两个节点之间有且仅有一条简单路径的无向图称为树。
等价定义：
- 有 $n$ 个节点，$n-1$ 条边的无向连通图
- 无向无环的连通图
- 任何边均为桥的连通图
- 没有环，且在任意不同两点间添加一条边之后所得图含唯一的一个环的图
根：
树根：树中的一个节点。（确定树根后的有根树能引申出许多其它概念）
无根树：没有固定根节点的树。
有根树：指定一个节点为根的树。
只对于有根树而言的概念：
- 父节点：对于除根以外的每个节点，定义为从该节点到根路径上的第二个节点。 根结点没有父节点。
- 祖先节点：一个结点到根节点的路径上，除了它本身外的节点。根节点没有祖先。
- 最近公共祖先：两个点的公共祖先里面，离根最远的那个。
- 子节点：如果 $u$ 是 $v$ 的父亲，那么 $v$ 是 $u$ 的子节点。
- 节点的深度：到根结点的路径上的边数（一般为边数 $+1$）。
- 树的高度：所有结点的深度的最大值。
- 兄弟节点：同一个父亲的多个子节点互为兄弟。
- 后代节点：子节点和子节点的后代。
- 子树：删掉与父亲相连的边后，该节点所在的图。
既适用无根树又适用有根树的概念：
- 森林：每个联通块都是树的图（注：树也是森林）。
- 生成树：一个无向联通图（可以有环）的生成子图，同时要求是树。
- 叶子节点：度不超过 $1$ 的节点。
- 树的直径：树上最长的任意两节点之间的简单路径
- 树的重心：对于树上的每一个点，计算以其为根时所有子树中最大的子树节点数，这个值最小的点就是这棵树的重心。
注：叶子节点既是无根树又是有根树的概念。比如：链，有两个叶子节点，而与它怎么画无关。
特殊的树：
- 链：满足与任一节点相连的边不超过 $2$ 条的树称为链。
- 菊花图：满足存在 $u$ 使得所有除 $u$ 以外结点均与 $u$ 相连的树。
- 二叉树：每个节点最多只有两个子节点的有根树。
二叉树：
（二叉树还存在有特殊的二叉树，限于篇幅不在此介绍）
二叉树是特殊的有根树，具有很多特殊的性质。
只对于二叉树的概念：
- 左右儿子：对任一节点两个的子节点任意编序，其中一个为左儿子，另一个即为右儿子。
- 完全二叉树：只有最下面两层结点的度数可以小于 $2$，且最下面一层的结点都集中在该层的最左侧 $\Leftrightarrow$ 对树中的节点按从上至下、从左到右的顺序进行编号，如果编号为 $i$ 的节点与满二叉树中编号为 $i$ 的节点在二叉树中的位置相同。
- 满二叉树$/$完美二叉树：所有叶节点的深度均相同的二叉树 $\Leftrightarrow$ 节点数$=2^{\text{树的高度}}-1$。
- 完整二叉树：每个节点的子节点数量均为 $0$ 或者 $2$ 的二叉树。
注：满二叉树和完整二叉树定义有歧义，不同教材定义不一致。有的教材，将满二叉树定义成完整二叉树。
图的存储：
直接存：
用一个结构体存储 $(u,v,w)$。
邻接矩阵：
用 $c[x][y]$ 表示 $(x,y,c[x][y])$。
邻接表：
把以一个点为起点的边存在这个点所对应的集合中。
有向图只存在起点，无向图两个端点都要存。
vector：
采用 vector 实现：
1 | vector<edge> p[N]; |
链式前向星：
采用链表实现：
1 | void add(int u,int v,int w){ |