5.1 什么是图

1.定义：

• 表示的是 多对多的关系。
  线性表： 一对一。 树：一对多。

• 包含： 一组顶点，用V（Vertex）表示顶点集合。
  一组边：通常用E（Edge）表示边的集合。

2.抽象数据类型：

常用： 无向图，有向图。

3.用邻接矩阵来表示图。

好处：
直观、简单、好理解
方便检查任意一对顶点间是否存在边
方便找任一顶点的所有“邻接点”(有边直接相连的顶点)
方便计算任一顶点的“度”(从该点发出的边数为“出 度”，指向该点的边数为“入度”)
无向图:对应行(或列)非0元素的个数
有向图:对应行非0元素的个数是“出度”;对应列非0元素的 个数是“入度”

不好的地方：
浪费空间 —— 存稀疏图(点很多而边很少)有大量无效元素
对稠密图(特别是完全图)还是很合算的
浪费时间 —— 统计稀疏图中一共有多少条边

4. 使用邻接表来表示一个图
   邻接表:G[N]为指针数组，对应矩阵每行一个链表， 只存非0元素