图的概念
图 G 由顶点集 V 和边集 E 组成，记为 G=(V, E)，其中 V(G) 表示图 G 中顶点的有限非集；E(G) 表示图 G 中顶点之间的关系（边）的集合。
注意：图不可以是空图，也就是说图中不能一个顶点都没有，但是边集可以为空
有向图
边 E 是有向边的有限集合。入度和出度分别等于边数
无向图
边 E 是无向边的有限集合。无向图的度之和为边数的两倍
简单图
- 不存在重复的边
- 不存在顶点到自身的边
多重图
图 G 中某两个结点之间的边数多余一条，又允许顶点通过同一条边和自己关联。多重图的定义与简单图相对。
完全图（简单完全图）
无向完全图：在无向图中，任意两个顶点之间都存在边。含有 n(n-1)/2 条边
有向完全图：有向图中，任意两个顶点之间都存在方向相反的两条弧。含有 n(n-1) 条有向边
子图
两个图 G = (V, E) 和 G’ = (V’, E’)，若 V’ 是 V 的子集，且 E’ 是 E 的子集，则称 G’ 是 G 的子图
连通、连通图和连通分量
- 无向图中，若从顶点 v 到顶点 w 由路径存在，则称 v 和 w 是连通的。若图中任意两个顶点都是连通的，则为连通图。
对于边数 e：
- e < n-1非连通图
- e > n-1 有环
e = n-1 连通图
极大连通子图：子图是无向图连通分量，极大要求该连通子图包含其所有的边
- 极小连通子图：既要保持图连通，又要使得边数最少的子图
强连通图、强连通分量
有向图中，从顶点 v 到 w 之间相互都有路径，则为强连通的。
生成树和生成森林
连通图的生成树是包含图中全部顶点的一个极小连通子图。
若图中顶点数为 n ，则它的生成树含有 n-1 条边。
砍掉一条边，立马变成非连通图。
加上一条边，立马变成环
边的权和网
图中，每条边都可以标上具有某种含义的数值，该数值成为边的权值。带权值的图称为有权图，或者网
稠密图、稀疏图
|E|<|V|log|V| 时，为稀疏图
路径、路径长度和回路
顶点 p 到 q 一条路径为 p 到 q 所经过的所有顶点。路径上边的数目为路径长度。
简单路径、简单回路
路径序列中，顶点不重复出现的路径为简单路径。
除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单路径。
距离
v 到 w 路径存在，则此路径长度为其之间的距离，若不存在则记为 ∞
有向树
顶点的入度为 0、其余顶点入度均为 1 的有向图。