一、图（Graph）
和树比起来，图是一种更加复杂的非线性表结构。
树中的元素我们称为节点，图中的元素我们就叫做顶点（vertex）。图中的一个顶点可以与任意其他顶点建立连接关系。这种建立的关系叫做边（edge），一个顶点和其他顶点有多少连线，我们称之为度（degree）。
图有好几种，无向图（双向箭头），有向图（单向箭头），加权图（带有权重）…
二、图的存储方式
一.邻接矩阵存储（Adjacency Matrix，适合小数据量存储）
这张图刚开始学习的人可能会一脸懵逼，我觉得这张图有一些不恰当的地方，比如不应该用数字表示图，再用矩阵去表示图的关系，很容易让人陷入去计算矩阵的误区。
下面这张图就比较合理，看得懂下面这张图，看懂上面的图不成问题。
邻接矩阵存放图有一个很大的缺点，就是会浪费掉很多的空间，比如无向图，其实有一半都表示的是相同的信息，另外如果图有很多顶点（对应矩阵有很多行），但是行与行之间的关系并没有那么密切，比如微信用户有几亿，但是一般人的好友也就几百个，用邻接矩阵来存储浪费的空间不可想象。
邻接矩阵也有优点，存储方式简单，在获取两个顶点的关系的时候非常高效，对于小数据量的图来讲，邻接矩阵是很好的存储方式
二.邻接表存储方法（Adjacency List）
邻接表比较像散列表（哈希表）中的链式法。
1、无向邻接表
2、有向邻接表
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: