1.5 本章要点

•图是对象之间逐对关系的一种表示形式，例如社交网络中的朋友关系、Web页面之间的超链接关系或任务之间的依赖关系。

•图由一组顶点和一组边组成。在无向图中，边是没有方向的；在有向图中，边是有方向的。

•如果图中边的数量m大致与顶点的数量n呈线性关系，那么这种图就是稀疏图。如果图中边的数量m大致与顶点的数量n呈平方关系，那么这种图就是稠密图。

•图的邻接列表表示形式维护图的顶点数组和边数组，彼此之间以一种自然的方式实现交叉引用，它所需要的空间与顶点和边的总数量呈线性关系。

•图的邻接矩阵表示形式为每一对顶点维护1个位，用于记录它们之间是否存在一条边。这种表示形式所需要的空间与顶点的数量呈平方关系。

•邻接列表表示形式适用于稀疏图以及那些涉及图的探索的应用。