二二：图的学习、图的概念、图的深度和广度优先遍历

一、为什么要有图

1、 前面我们学了线性表和树；
2、 线性表局限于一个直接前驱和一个直接后继的关系；
3、 树也只能有一个直接前驱也就是父节点；
4、 当我们需要表示多对多的关系时，这里我们就用到了图；

二、图的举例说明

图是一种数据结构，其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为顶点。如图：

三、图的常用概念

1、 顶点(vertex)；
2、 边(edge)；
3、 路径；
4、 无向图(右图)；
5、 有向图；

6、 带权图；

四、图的表示方式

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

4.1 邻接矩阵

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