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