§7 图

§7.1 图的基本概念

图都是由顶点和边构成的，形式化定义为 $G=(V,E)$。

多数概念都很好理解，这里只写几个容易错的：

对于无向图，每个顶点的度定义为以该顶点为一个端点的边数。对于有向图，度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。握手定理：$e=\cfrac{1}{2}\sum d_{u}$。

边数 $e\ll n\log_{2}n$ 的图是稀疏图，否则是稠密图。

路径长度 是指一条路径上经过的边的数目。

带权图也称网。本书中规定所有边的权均为非负数。

如果不带权，则 $A{ij}=1$ 表示有边，$A{ij}=0$ 表示没有边；

如果带权，$A{ij}=0$ 表示 $i=j$，$A{ij}=\infty$ 表示没有边，否则是这条边的边权。

这适合稠密图，空间 $\mathrm{O}(n)$，判断边是否存在 $\mathrm{O}(1)$。

链式存储结构，具体是对图中每个顶点建立一个带头节点的单链表，把该顶点的所有相邻点串起来，总共建立 $n$ 个。每个单链表中每个节点包括：

这适合稀疏图，建立的复杂度是 $\mathrm{O}(n+e)$。