转载自https://github.com/Snailclimb/JavaGuide（添加小部分笔记）感谢作者!

• 图是一种较为复杂的非线性结构
• 线性数据结构的元素满足唯一的线性关系，每个元素（除第一个和最后一个外）只有一个直接前驱和一个直接后继
• 树形数据结构的元素之间有着明显的层级关系
• 图形结构的元素之间的关系是任意的
  • 图就是由顶点的有穷非空集合和顶点之间的边组成的集合，通常表示为：G（V，E），其中，G表示一个图，V表示顶点的集合，E表示边的集合
  • 下面显示的即图这种数据结构，而且还是一张有向图

图的基本概念 #

顶点 #

• 图中的数据元素，我们称之为顶点，图至少有一个顶点（有穷非空集合）
• 对应到好友关系图，每一个用户就代表一个顶点

边 #

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

度 #

• 度表示一个顶点包含多少条边
• 有向图中，分为出度和入度，出度表示从该顶点出去的边的条数，入度表示从进入该顶点的边的条数
• 对应到好友关系图，度就代表了某个人的好友数量

无向图和有向图 #

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

有的关系是有方向的，比如父子关系，师生关系，微博的关注关系，A是B的爸爸，但B肯定不是A的爸爸，A关注B，B不一定关注A。在这种情况下，我们就用带箭头的边表示二者的关系，这样的图就是有向图。

无权图和带权图 #

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

对于一个关系，如果我们既关心关系的有无，也关心关系的强度，比如描述地图上两个城市的关系，需要用到距离，那么就用带权图来表示，带权图中的每一条边一个数值表示权值，代表关系的强度。

下图就是一个带权有向图。

图的存储 #

邻接矩阵存储 #

• 邻接矩阵将图用二维矩阵存储，是一种比较直观的表示方式
• 如果第i个顶点和第j个顶点有关系，且关系权值为n，则A[i] [j] = n
• 在无向图中，我们只关心关系的有无，所以当顶点i和顶点j有关系时，A[i] [j]=1 ; 当顶点i和顶点j没有关系时，A[i] [j] = 0 ，如下图所示
  无向图的邻接矩阵是一个对称矩阵，因为在无向图中，顶点i和顶点j有关系，则顶点j和顶点i必有关系
• 有向图的邻接矩阵存储 邻接矩阵存储的方式优点是简单直接（直接使用一个二维数组即可），并且在获取两个顶点之间的关系的时候也非常高效*直接获取指定位置的数组元素。但是这种存储方式的确定啊也比较明显即 比较浪费空间

邻接表存储 #

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

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

  • 无向图的邻接表存储
  • 有向图的邻接表存储

• 邻接表中存储的元素的个数（顶点数）以及图中边的条数

  • 无向图中，邻接表的元素个数等于边的条数的两倍，如下图 7条边，邻接表存储的元素个数为14 （即每条边存储了两次）

    

  • 有向图中，邻接表元素个数等于边的条数，如图所示的有向图中，边的条数为8，邻接表

图的搜索 #

广度优先搜索 #

• 广度优先搜索：像水面上的波纹一样，一层一层向外扩展，如图

• 具体实现方式，用到了队列，过程如下

  1. 初始状态：将要搜索的源顶点放入队列

  2. 取出队首节点，输出0，将0的后继顶点（全部）（未访问过的）放入队列

  3. 取出队首节点，输出1，将1的后继顶点（所有）（未访问过的）放入队列

     截止到第3步就很清楚了，就是输出最近的一个结点的全部关系节点

  4. 取出队首节点，输出4，将4的后继顶点（未访问过的）放入队列

  5. 取出队首节点，输出2，将2的后继顶点（未访问过的）放入队列

  6. 取出队首节点，输出3，将3的后继顶点（未访问过的）放入队列，队列为空，结束

  7. 总结 先初始化首结点，之后不断从队列取出并将这个结点的有关系的结点 依次放入队列

深度优先搜索 #

• 深度优先，即一条路走到黑。从源顶点开始，一直走到后继节点，才回溯到上一顶点，然后继续一条路走到黑
• 和广度优先搜索类似，深度优先搜索的具体实现，用到了另一种线性数据结构—栈

1. 初始状态，将要搜索的源顶点放入栈中

2. 取出栈顶元素，输出0，将0的后继顶点（未访问过的）放入栈中

3. 取出栈顶元素，输出4（因为后进先出），将4的后继顶点（未访问过的）放入栈中

4. 取出栈顶元素，输出3，将3的后继顶点（未访问过的）放入栈中

   ---

   其实到这部就非常明显了，即 前面元素的关系元素，大多都是被一直压在栈底的，会一直走走到 源顶点的直系关系顶点没有了，再往回走

5. 取出栈顶元素，输出2，将2的后继顶点（为访问过的）放入栈中

6. 取出栈顶元素，输出1，将1的后继顶点（未访问过的）放入栈中，栈为空，结束