6.2 图的存储及基本操作

6.2.1 邻接矩阵法

时间复杂度 $O(|V|^{2})$

$\begin{bmatrix}0&1&0\ 1&0&0\ 0&1&0\end{bmatrix}$

6.2.2 邻接表法

存储稀疏图

有向图存储空间 $O(|V|+|E|)$

无向图存储空间 $O(|V|+2|E|)$

6.2.3 十字链表

存储有向图

向下是入，向右是出

空间 $O(|V|+|E|)$

6.2.4 邻接多重表

存储无向图

（数据，相连的第一条边）

空间 $O(|V|+|E|)$

n 个顶点，e 条边的有向图。

查找有向图某顶点的入度 $O(n+e)$

查找有向图某顶点的出度 $O(n)$