图 #
- 图的概念
- 图的存储结构
图的概念 #
图表示了一种多对多的关系，相比线性表的一对一以及树结构的一对多，图的使用范围更广泛结构也更复杂，我们先给出图的定义，再了解图的一些基本术语。
图(Graph)是由一组顶点和一组边的集合构成，记为G=(V,E)， 其中V是vertex，即是顶点，E是edge，即为边。因此，V(G)和E(G)通常分别表示图G的顶点集合和边的集合。一般图有3种要素:
在图的3种要素的基础上衍生了更多相关的概念和划分，
图的存储结构 #
图有两种存储方式，邻接矩阵和邻接表。
邻接矩阵是指用矩阵来表示图，它采用矩阵来描述图中顶点之间的关系，假设图中顶点数为n,则邻接矩阵定义为：
下面是一个简单的有向图和邻接矩阵：
邻接表是图的一种链式表示方法，相对于图来讲，它没有那么直观，但所需要存储的数据更少，更省空间。下图中由于B本身没有指向别的顶点的边，所以邻接表中少了这一项，对于越大型、连接越稀疏的图，这种存储方式在存储方面的优势越大。
小结 #
习题 #
- 邻接表除了更方便存储外，你还能想到什么优点？
- 尝试找一张简单的图实现邻接表
