文章目录

• 图的基本概念

• 1、图的定义
• 2、特殊的图
• 3、图的分类
• 4、图的相关术语
• 5、图的存储结构

• 5.1 邻接矩阵
• 5.2 邻接表

• 图的实现

• 邻接矩阵方式实现
• 邻接表方式实现

• 图的搜索/遍历

• 深度优先搜索方法（DFS）

• 深度优先搜索主要思想

• 广度优先搜索方法（BFS）

• 广度优先搜索主要思想

为什么要用到图：
数处理一对多的关系，用图可以处理多对多的关系。

图由一组顶点和一组能够将两个顶点相连的边组成。图是一种数据结构，其中结点可以具有零个或多个相邻元素。两个结点之间的连接成为边，结点在图中也称为顶点。

例如：下面三幅都是图

（1）自环：即一条连接一个顶点和其自身的边；

（2）平行边：连接同意对顶点的两条边

按照连接两个顶点的边的不同，可以把图分为以下两种
无向图：边仅仅连接两个顶点，无任何指向
有向图：边连接两个顶点，并且具有方向

相邻顶点：当两个顶点通过一条边相连时，称之为相邻，并且称这条边依附于这两个顶点
子图：一副图的所有边的子集（包含边所依附的顶点）组成的图
度：某个顶点的度就是依赖于该顶点的边的个数
路径：是由边顺序连接的一系列的顶点组成
环：是一条至少含有一条边且终点和起点相同的路径
连通图：如果途中任何一个顶点都存在一条路径到达另外一个顶点，那么==这幅图就称之为连通图。
连通子图：一个非连通图由若干连通的部分组成，每一个连通的部分都可以成为该图的连通子图。
权(Weight)：有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权(Weight)。

要表示一幅图，只需要表示清楚以下两部分即可：
1、图中所有的结点
2、所有连接顶点的边

常见的图的存储结构有如下两种：邻接矩阵和邻接表

5.1 邻接矩阵

邻接矩阵是表示图形中顶点间相邻关系的矩阵，对于n个顶点的图而言，可以使用二维数组的横坐标和纵坐标表示图中的某个顶点，同时根据带不带权，有向图还是无向图，又可以分为很多类别：邻接矩阵实现不带权无向图，带权无向图，不带权有向图，带权有向图。

不带权邻接矩阵中二维数组存储的值分别为1和0。1代表两个顶点之间存在边，0代表两个顶点间不存在边。
带权邻接矩阵中二位数组存储的值表示权值，大于0表示两个顶点之间存在边，并且这个边的大小等于权值的大小，等于0时表示没边。

这是不带权无向图的邻接矩阵，例如：A与B之间存在边，所以arr[ A ][ B ] = 1;而又因为是无向图，所以arr[ A ] [ B ] = 1（通常邻接表竖直方向上的数值表示二维数组中的横坐标，水平方向上表示纵坐标）

这个是带权无向图的邻接矩阵，顶点A和B之间存在边，并且边的大小为5，所以arr[ A ][ B ] = 5，因为是无向图，所以互通的两顶点之间的边是一样的。

分析：无向图含边顶点间的指向是双向的，也就是说共享一条边。所以在矩阵中，是按照右对角线对称的。

下面是不带权有向图的邻接矩阵，例如：A和B之间是有边的，但指向却只有A顶点指向B顶点，所以在矩阵中，只有arr[ A ][ B ] = 1；而arr[B] [A ] 不等于1；

下面是带权有向图的邻接矩阵，A和B之间是有边的，但指向却只有A顶点指向B顶点，所以在矩阵中，只有arr[ A ][ B ] = 5；而arr[B] [A ] 不等于5；

使用邻接矩阵实现图的缺点：
使用邻接矩阵这种弄存储方式的空间复杂度是N^2，所以当处理的问题规模比较大的话，内存空间极有可能不够用，可以发现，当很多边不存在的时候，内存空间同样需要存储数据，这样会造成空间的一定损失。

5.2 邻接表

顺序存储结构就存在预先分配内存可能造成存储空间浪费的问题，于是引出了链式存储的结构。同样的，可以考虑对边或弧使用链式存储的方式来避免空间浪费的问题。 邻接表的实现只关心存在的边，不关心不存在的边，因此没有空间的浪费，邻接表由数组+链表组成。
邻接表由表头节点和表节点两部分组成，图中每个顶点均对应一个存储在数组中的表头节点。如果这个表头节点所对应的顶点存在邻接节点，则把邻接节点依次存放于表头节点所指向的单向链表中。

构建图的邻接表实现的关键点在于“：你所建立的图的邻接表的对象是什么！
邻接链表的创建首先我们需要确定邻接表的对象，可以用顶点作为邻接链表的对象，也可以用边作为邻接链表的对象。

无向图

表头结点用数组来存储，并且表头结点中的数据域表示顶点，表头结点中的指针域指向表结点中的第一个结点。表结点中的数据域存储的是与头结点有边关系的结点的下表，表结点中的指针与指向下一个表结点。
补充：对于无向图来说，使用邻接表进行存储也会出现数据冗余的现象。例如上图中的A头结点指向了B结点，但B结点也能够指向A结点。

有向图

表头结点用数组来存储，并且表头结点中的数据域表示顶点，表头结点中的指针域指向表结点中的第一个结点。表结点中的数据域存储的是与头结点有边关系的结点的下表，表结点中的指针与指向下一个表结点。
有向图中就没有出现数据冗余的情况。

带权图

对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可

邻接矩阵方式实现

无向图的邻接矩阵实现

测试代码：

结果如下：
邻接矩阵：
[0, 1, 1, 1, 0]
[1, 0, 1, 1, 1]
[1, 1, 0, 0, 0]
[1, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
边的数目7
顶点个数5
获取顶点B所对应的索引1
获取索引4对应的顶点D
深度优先遍历后的结果：
ABCED
广度优先遍历后的结果：
ABCED

补充：无论是带权还是不带权只需要更改insertEdges()方法中的weight参数即可，不带权，1表示有边，0表示无边；带权，0表示无边，其他数值表示边的大小。

有向图的邻接矩阵实现

有向图时，只要将上面无向图的实现方法中的insertEdges()方法改为如下，表示两顶点之间的指向是单向的：

测试代码：

结果如下：
邻接矩阵：
[0, 1, 1, 0, 0]
[0, 0, 1, 1, 1]
[1, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[1, 0, 0, 0, 0]
边的数目7
顶点个数5
获取顶点B所对应的索引1
获取索引4对应的顶点E
深度优先遍历后的结果：
ABCED
广度优先遍历后的结果：
ABCED

邻接表方式实现

第一种方式：将顶点作为图的对象

• 顶点类

• 图类

• 测试类

• 测试过程与结果

第二种方式：将边作为图的对象
同样的需要设置定点类，不过这里的顶点类主要用来辅助构建图。

测试类

测试及结果如下：

个人觉得图的构建的所有过程写在构造函数内不好看，于是拆分到了各个方法中，如下：

• 头节点类

• 边表结点类

• 图类

• 测试类

• 测试及结果

深度优先搜索（DFS）

深度优先搜索主要思想

假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

无向图深度优先图解：

分析：访问顺序和过程如下：
A =>C =>B => D =>F =>G =>E
访问过程：
（1）访问A。
（2）访问C。访问的是A的邻接点，并且由添加顶点顺序决定是访问临界点中的哪个点，因为C排在D、F之前，所以先访问C。
（3）访问B。访问的是C的临界点，同上，因为B排在D之前，所以先访问B，而A已经被访问过了，所以不会再访问。
（4）访问D。访问B后，B无任何邻接点，所以递归返回至C点，开始访问未被访问过的D点。
（5）访问F。D无邻接点，递归返回至C，而C点的所有邻接点都被访问过了，所以再次返回值A，A的邻接点中有F点未被访问过，所以访问F点。
（6）接下来就是依次访问G，E点。

有向图深度优先图解：

分析：从顶点A开始。
A=>B =>C =>E =>D =>F =>G
访问过程如下：
（1）访问A。
（2）访问B。A的唯一一个邻接点
（3）访问C。访问B点之后，按顶点顺序，先访问C。
（4）访问E。C的为一个有指向的邻接点。
（5）访问D。访问E后，因为B已经访问过了，所以访问还未被访问到的D点
（6）访问F。再访问完D点后，D点的邻接点C被访问过了，递归回到E，再递归回到C，再递归回到B点，访问未被访问过的F点
（7）访问G。访问完F后，访问G点。

广度优先搜索算法(Breadth First Search)，又称为"宽度优先搜索"或"横向优先搜索"，简称BFS。

广度优先搜索主要思想

从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。

简单来说就是以最开始的顶点为起点，依次访问预期路径相通且路径长度为1，2，3…的顶点。

无向图广度优先图解

分析：
A =>C =>F =>B =>D =>G =>E
（1）访问A。
（2）依次访问C、D、F。A有两个邻接点，C和F，C排在F前面，所以先访问C,再访问F。
（3）依次访问B、G。在访问完C、D、F之后，再次访问他们的邻接点。
（4）最后访问E。

有向图广度优先图解

分析：A =>B =>C =>E =>E =>F =>D =>G
（1）访问A。
（2）访问B。
（3）依次访问C、E、F。
（4）依次访问D、G。

两种遍历的具体实现均在图的实现那节