数据结构秘籍（二）图（含图的概念、存储以及图的两大搜索）

1 引言

线性数据结构的元素满足唯一的线性关系，每个元素（初第一个和最后一个外）只有一个直接前趋和一个直接后继。树形数据结构的元素之间有着明显的层次关系。但是图形结构的元素之间的关系是任意的。

什么是图？

简单来说，图就是由顶点的有穷非空集合和顶点之间的边组成的集合。通常表示为：G（V,E），其中，G表示一个图，V表示顶点的集合，E表示边的集合。

上图所展示的就是图，而且是一个有向图（带箭头） 

2 图的基本概念

拿好友关系举例

2.1 顶点

图中的数据元素我们称之为顶点，图中至少有一个顶点（非空有穷集合）

对应到好友关系图，每一个用户就代表一个顶点。

2.2 边

顶点之间的关系用边表示。

对应到好友关系图，两个用户是好友的话，那两者之间就存在一条边。

2.3 度

度表示一个顶点包含多少条边，在有向图中，还分为出度和入度，出度表示从该顶点出去的边的条数，入度表示进入该顶点的边的条数。

对应到好友关系图，度就代表了某个人的好友数量。

2.4 无向图和有向图

边表示的是顶点之间的关系，有的关系是双向的，比如同学，A是B的同学，那么B也肯定是A的同学，那么在表示A和B的关系时，就不用关注方向，用不带箭头的边表示，这样的图就是无向图。

有的关系是有方向的，比如抖音，我关注了你，你没有关注我，这样我们之间的关系就是单向的，我们用箭头表示二者之间的关系，这样的图就是有向图。

2.5 无权图和带权图

对于一个关系，如果我们只关心关系的有无，而不关心关系有多强，那么就可以用无权图来表示二者的关系。

对于一个关系，如果我们既关心关系的有无，也关心关系的强度，比如某某某的好感度，你对人家好感度百分百，人家对你好感度百分之零（一个悲伤的故事），那么就可以用带权图来表示，带权图中每一条边用一个数值表示权值，代表关系的强度。

把上面的有向图进行加工就是一个带权有向图

3 图的存储

3.1 邻接矩阵存储

邻接矩阵将图用二维矩阵存储，是一种较为直观的表示方式。

如果第i个顶点和第j个顶点之间有关系，且关系权值为n，则A[i][j]=n。

在无向图中，我们只关心关系的有无，所以当顶点i和顶点j有关系时，A[i][j]=1，当顶点i和顶点j没有关系时，A[i][j]=0。如下图所示。

值得注意的是：无向图的邻接矩阵是一个对称矩阵，因为在无向图中，顶点i和顶点j有关系，那么就必定是双方的。

邻接矩阵存储的方式优点是简单直接（直接用一个二维数组即可），并且，在获取两个顶点之间的关系时也非常高效（直接获取指定位置的数组元素的值即可）。但是吧，这种存储方式的缺点也很明显，那就是比较浪费空间。

3.2 邻接表存储

针对上面邻接矩阵比较浪费内存空间的问题，诞生出了另外一种存储方法--邻接表。

邻接链表使用一个链表来存储某个顶点的所有后继相邻顶点。对于图中每个顶点Vi，把所有邻接于Vi的顶点Vj链成一个单链表，这个单链表称为顶点Vi的邻接表。如下图所示：

可以数一数邻接表中所存储的元素的个数以及图中边的条数：

在无向图中，邻接表元素个数等于边的条数的两倍，如左图所示的无向图中，边的条数为7，邻接表存储的元素个数为14。

在有向图中，邻接表元素个数等于边的条数，边的条数为8，那么邻接表存储的元素个数就为8. 

4 图的搜索 

4.1 广度优先搜索

广度优先搜索是一层一层向外扩展的

广度优先搜索的具体实现方式用到了之前学过的线性数据结构--队列。具体过程如下所示 

4.2 深度优先搜索

深度优先搜索就是从原顶点开始，一直走到没有后继节点，才回溯到上一顶点，然后继续往下走。

 

注意：搜索顺序是不唯一的，如果给出了链表或矩阵的存储方式，如下就是用单链表存储，那么搜索顺序就是固定的。 

 深度优先搜索的具体实现用到了另一种线性数据结构--栈。（队列和栈可以从我线性数据结构一文中了解数据结构秘籍（一）线性数据结构（数组、链表、栈、队列一次看完）-CSDN博客）过程如下：