【复习】 单源最短路径问题

发布于 7 天前  5 次阅读


前置知识

图(树)的存储——邻接表

邻接表是树与图结构的一般化存储方式,可以看成“带有索引数组的多个数据链表”构成的结构集合。

什么意思?

如图所示,这是一个存储了6个数据节点 v1~v6 的邻接表结构。这6个数据被分成4类,通过表头数组 head 可以定位到每一类所构成的链表进行遍历访问。

img

当需要插入新的数据节点时,我们可以通过表头数组 head 定位到新的数据节点所属类别的链表表头,将新数据在表头位置插入。如下图所示,在邻接表中插入了属于第五类的新数据节点 v7 。

img

具体的来说。。。

在一个具有 n 个点 m 条遍的有向图结构中,我们可以把每条边所属的“类别”定义为该边的起点编号。这样所有边被分成 n 类,其中第 x 类就由“从 x 出发的所有边”构成。通过表头 head[x] ,我们很容易定位到第 x 类所对应的链表 ,从而访问从点 x 出发的所有边。

img

如图是在领接表中插入一张5个点、6条边的有向图之后的状态。这6条边按照插入的顺序依次是(1,2),(2,3),(2,5),(3,5),(5,4),(5,1)。左侧展示了这个邻接表存储的宏观信息,右侧展示了采用“数组模拟链表”的实现方式时,内部数据的实际存储方式。 head 与 next 数组中保存的是“ ver 数组的下标”,相当于指针,其中0表示指向空。ver 数组存储的是每条边的终点,是真实的图数据。