存图

讨论有向图与无向图的存储方式，以实现各类图论算法。

邻接表

顶点表与链表组成的数据结构。每个顶点作为链表的头，存储相连的边。适合稀疏图。查询两个顶点间是否有边困难。

链式前向星

数组模拟邻接表，因实现容易广泛用于竞赛，且由于边带有编号的性质，有时很有用，如获取反边。

邻接矩阵

二维矩阵，\(A[i][j]\) 有值 = \(i\) 到 \(j\) 有边。适合稠密图。无向图 \(A[i][j]=A[j][i]\)，可以压缩存储，节省一半空间。删除顶点困难。

只有邻接矩阵表示方式唯一。

十字链表

存有向图，解决了邻接表顶点入度计算困难的问题。每个顶点同时存入边和出边表。与邻接表对应，如果说邻接表只存了出边（顶点 \(v\) 的指针存的链表是以该点为起点的所有边），那么十字链表还存了入边，即以顶点 \(v\) 为终点的所有边。一条边只存一次，所以这条边的头尾顶点都是可以确定的，且头顶点的出边表指向这条边，尾顶点的入边表也指向这条边。

顶点定义：

| data | firstIn | firstOut |

边定义：

| tailvex | headvex | hlink | tlink | info |

既然邻接表求出度方便（即链表长度），那么十字链表求入度方便是显然的。

邻接多重表

存无向图，解决了邻接表存无向图时需要存两条边，删改边需要同时修改两条边的问题。每条边只存一次，但同时存头尾顶点，用两个指针分别指向两个顶点的下一条边。对应邻接表只存储一个方向的边，邻接多重表通过添加指针的方式让两个顶点地位相同。

顶点定义：

| data | firstedge |

边定义：

| mark | ivex | jvex | ilink | jlink | info |

由于一条边只存一次，删改都只要对一个对象操作。