图的基本介绍和表示方式

图的基本介绍

为什么要有图这个基本数据结构?

我们还学习过线性表（数组、队列、链表和栈）和树，但是我们可以发现，线性表局限于一个直接前驱（就是只能有唯一一个前面的结点）和一个直接后继的（唯一一个后面的结点）关系。树也只能有一个直接前驱也就是父节点。但是当我们如果想要表示多对多的关系时，前面所学习的数据结构就不能满足我们的需求了，这时候我们就需要图这个数据结构

图的举例说明

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

图的常用概念

顶点：图的每个结点就是顶点，例如：B

边(edge)：图中两个顶点之间的线就叫做边，例如：A和B之间的连线

路径：路径就是从某个顶点到另一个顶点索要经过的所有顶点，例如从 D -> C 的路径有：①D->B->C ② D->A->B->C

无向图：就是两个相邻顶点间没有指明方向，例如：可以从B到A，也可以从A到B

有向图

带权图。例如下图中两顶点中的权就是两地的距离

图的表示方式

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

邻接矩阵

二位数组中的0表示的是两节点之间不能直接连通，1表示能直接连通

邻接表

邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在,会造成空间的一定损失.

邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组+链表组成