java数据结构和算法——图的基本介绍

一、为什么要有图

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

二、图的举例说明

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

三、图的常用概念

• 顶点(vertex)：结点也可以称顶点。（如上图）

• 边(edge)：两个结点之间的连接。（如上图）

• 路径：比如从 D -> C 的路径有**（如上图）** 1)、 D->B->C 2）、D->A->B->C

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

• 有向图： 顶点之间的连接有方向，比如A-B，只能是 A-> B ，不能是 B->A 。（如上图）

• 带权图：这种边带权值的图也叫网.（如下图）

四、图的表示方式

1、图的表示方式有两种：

• 二维数组表示（邻接矩阵）。
• 链表表示（邻接表）。

2、邻接矩阵

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

图形说明：

• 矩阵中第一行第一列表示：0和0本身，有0表示。
• 矩阵中第一行第二列表示：0和1可以直接连通，用1表示
• 矩阵中第一行第三列表示：0和2可以直接连通，用1表示
• 矩阵中第一行第四列表示：0和3可以直接连通，用1表示
• 矩阵中第一行第五列表示：0和4可以直接连通，用1表示
• 矩阵中第一行第六列表示：0和5不可以直接连通，用0表示 。。。。。。。。 依此类推。

3、邻接表

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

图形说明:

• 标号为0的结点的相关联的结点为 1 2 3 4
• 标号为1的结点的相关联结点为0 4
• 标号为2的结点相关联的结点为 0 4 5
• 标号为3的结点相关联的结点为 0 5
• 标号为4的结点相关联的结点为 0 1 2 5
• 标号为5的结点相关联的结点为 2 3 4