图

图可以结合数组,链表,树一起来看

数组和链表
是线性表的数据结构,它的往前和往后都是固定的.

树
非线性表数据结构,但是他往前是固定的,往后是不固定的
树中的元素,我们叫做节点

图
非线性表数据结构,他往前和往后都不是固定的.
图中的元素,我们叫他顶点
两个顶点之间的线条,也就是他们存在的关系,我们叫边
如果这个边是有方向的,那么他就是一个有向图,反之,他就是无向图
如果这个边带有权重,那么他就是带权图
和一个顶点相连的边,我们叫他这个定点的度,
同理,在有向图中就会有入度和出度的概念

如何存储一个图

1.邻接矩阵(二维数组存储法)
用当前图的顶点组成的二维数组.
比如V0 - V1 ,那我们在二维数组中 (V0,V1)存1,同理因为是无向图(V1,V0) 也存 1.
但是因为是在无向图中是轴对称关系,所以,会浪费一半的元素.
万一这个图是稀疏图,那么浪费的会更多.而且受内存大小的限制

2.邻接表(链表存储法,哈希表存储法)
我们用顶点的个数构建一个数组,
然后用链表存储,和他有直接关系的的顶点(在有向图中,需要存指向的,无向图全存)