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
网友评论