图
图G（graph）由顶点集V（vertex）和边集E（edge）组成，记为G(V,E)
在图中，如果有边，那么此边的两端一定有点；否则不构成图
- 顶点的个数也称为图的阶
- 线性表可以是空表，树可以是空树，但图不能是空图，即顶点集V一定是非空集，但边集E可以为空集
无向图与有向图
若E是无向边（简称边）的有限集，则称G为无向图
- 边是顶点的无序对（一条边可以由一对无序的顶点表示），记为(v,w)或(w,v)，因为(v,w)=(w,v)
- 顶点v和顶点w互为邻接点
若E是有向边（简称弧）的有限集合，则称G为有向图
- 弧是顶点的有序对（一条边可以由一对有序的顶点表示），记为<v,w>，是一条从顶点v到顶点w的弧，v为弧尾，w为弧头（有箭头的一端）
- <v,w>也称v邻接到w，或w邻接自v
简单图与多重图
简单图：不存在重复边；不存在顶点到自身的边
多重图：与简单图相反
数据结构课程只讨论“简单图”
顶点的度、入度、出度
对于无向图：
- 顶点v的度指与该点相连的边的条数，记为TD(v)
- 全部顶点的度之和是边数的两倍
对于有向图：
- 入度是以顶点v为终点的有向边的数目，记为ID(v)
- 出度是以顶点v为起点的有向边的数目，记为OD(v)
- 顶点v的度等于其入度与出度之和，即TD(v)=ID(v)+OD(v)
- 所有顶点的入度之和=出度之和=|E|
顶点-顶点的关系描述
路径：一个顶点到另一个顶点的的路径是指顶点序列
回路：第一个顶点和最后一个顶点相同的路径称为回路或环
简单：即要求不重复
简单路径：一个路径中没有没有重复的顶点
简单回路：除了第一个顶点与最后一个顶点，其余顶点不重复的回路称为简单回路
路径长度：路径上边的数目
点到点的距离：两点之间最短路径的长度就是点到点的距离；若两点间不存在路径，那么记该距离为无穷\infty
连通：
- 无向图中，若两顶点之间有路径存在，则两顶点是连通的
若任意两个顶点都是连通的，那么称图G为连通图，否则称为非连通图 - 有向图中，若两顶卖之间既有正向路径，也有逆向路径，那么两顶点是强连通的
若任意两个顶点都是强连通的，那么称此图为强连通图 - 常见考点：对于n个顶点的无向图G
- 若G是连通图，则最少有n-1条边
- 若G是非连通图，则最多可能有C^2_{n-1}（有一个顶点与其他顶点都没有连接，而其他顶点组成完全图，n-1个里任选2个）
- 对于n个顶点的有向图G
- 若G是强连通图，则至少有n条边（形成回路）
子图
图G1的顶点集和边集都是图G的子集，那么称G1是G的子图
若G1和G的顶点集相同，那么称G1是G的生成子图
连通分量
无向图中的极大连通子图称为连通分量
有向图中的极大强连通子图称为强连通分量
生成树
连通图的生成树是包含图中全部顶点的一个极小连通子图
- 连通图的生成树不唯一
- 若图中顶点数为n，则生成树的边数是n-1
生成森林
在非连通图中，连通分量的生成树构成了非连通图的生成森林
边的权、带权图/网
边的权：在一个图中，每一条边都可以标上具有某种含义的数值，该数值称为该边的权值
带权图/网：边上带有权值的图称为带权图，也称网
带权路径长度：当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度
几种特殊形态的图
无向完全图：无向图中任意两个顶点之间都存在边
- 无向完全图的边总数为：C^2_n
有向完全图：有向图中任意两个顶点之间都存在方向相反的两条弧
- 有向完全图的边总数为：2C^2_n
稀疏图：边数很少的图
稠密图：与稀疏图相对的图
树：不存在回路，且连通的无向图
- n个顶点的树，则必有n-1条边
- 常见考点：n个顶点的图，若|E|>n-1，则一定有回路
有向树：一个顶点的入度为0，其余顶点的入度都为1的有向图，称为有向树
