数据结构--邻接表

回顾上节：  邻接矩阵--数组实现的顺序存储，空间复杂度高，不合适存储稀疏图。On^2

一、邻接表法（顺序+链式存储）

  无向图： 用一维数组存储顶点信息，使用指针存储顶点的第一条边/弧。对于边/弧，设置指针来指向下一个结点。

无向图和有向图的区别：

  无向图： 边界点的数量是2|E|，整体空间复杂度为  O（|V|）+  2|E|

  有向图：边结点的数量是|E|，整体空间复杂度为 O（|V|）+|E|

  思考：如何求顶点的度、出度、入度。

  无向图的度：遍历这个顶点相关的边链表。

  有向图：  出度：遍历这个顶点相关的边链表

                  入度：只能遍历所有结点的边链表

注意： 图的邻接表表示方式不唯一。

总结：