1.图

1.1 为什么需要图这种数据结构

线性表局限于一个直接前驱和一个直接后继的关系
树也只能有一个直接前驱也就是父节点
当我们需要表示多对多的关系时，即一个节点有多个前驱节点时,就用到了"图"

1.2 图概念

图是一种数据结构
#顶点 & 节点
节点也可以称为顶点。其中节点可以具有零个或多个相邻元素。

#边
两个节点之间的连接称为边。

#路径:  
比如从 D -> C 的路径有
1) D->B->C
2) D->A->B->C

#无向图：
顶点之间的连接没有方向，比如A-B,
即可以是 A-> B 也可以 B->A .

#有向图： 
顶点之间的连接有方向，比如A-B,
只能是 A-> B 不能是 B->A .

#带权图：
边带权值的图也叫网.

无向图.png 有向图.png 网--带权图.png

1.3 图的表示方式

图的表示方式有两种：
>> 二维数组表示（邻接矩阵）；
>> 链表表示（邻接表）。

1.3.1 邻接矩阵

邻接矩阵是表示图形中顶点之间相邻关系的矩阵，
对于n个顶点的图而言，矩阵是的row和col表示的是1....n个点。

邻接矩阵.png

1.3.2 邻接表

1.邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在,会造成空间的一定损失。
2.邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组+链表组成。

邻接表.png