转载自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,邻接表

图的搜索#
广度优先搜索#
广度优先搜索:像水面上的波纹一样,一层一层向外扩展,如图















如上,Eden区内存几乎被分配完全(即使程序什么都不做,新生代也会使用2000多K)
在给allocation2分配内存之前,Eden区内存几乎已经被分配完。所以当Eden区没有足够空间进行分配时,虚拟机将发起一次MinorGC。GC期间虚拟机又发现allocation1无法存入空间,所以只好通过分配担保机制,把新生代的对象,提前转移到老年代去,老年代的空间足够存放allocation1,所以不会出现Full GC(这里可能是之前的说法,可能只是要表达老年代的GC,而不是Full GC(整堆GC) ) 

