图的存储问题

图的存储问题

2019独角兽企业重金招聘Python工程师标准>>>

图，大体有两类存储方式。简单说可以分为 索引方式和 结构方式两种。
索引方式表示，顶点或边，我们使用值来描述，其存储位置信息（不一定是直接存储位置信息）。
而结构方式，在于顶点或边之间的关联，被结构固化。不需要通过信息来描述图的结构本身。信息只需要描述结构内容的存在与否。
例如：我们对二叉树有两种数据组织形式。
1、由于2叉树的性质，我们可知，n层二叉树，最多需要 个存储结点。如果我们始终保持根比叶子存储更靠前的规则，则我们可以将二叉树的关联结构
固化在对存储的描述中。我们令第0层的结点存储在 [1]的位置。第1层的结点，存储在[2][3]两个位置。由此，第m层存储的位置为 之间。
这种方式，适用于图的结构固定的情况，简称这种方法为 “结构存储法”。但不是说只有固定的图的机构才能使用这种方法。
例如我们已知系统最多有N个顶点，对于无向图，则我们可以构造 ;个存储空间。任意i位置，我们可以通过一个公式求出唯一的一个(x,y),有x < y,

此时，该位置标记1时，表示存在 x 到 y的边，为0时，表示不存在该边。简称这种方式为“边存在标记法”

 

2、除了上述方式，我们还可以直接保存二元关系的信息，例如，每个存储单元，都包含两个顶点内容x,y，该存储单元整体则表示存在(x,y)的变。简称这种方法为“ 二元关联存储法”。这种方式存储结构就是线性扁平的，同时存储位置和图的结构无关，此区别上述“边存在标记法”，后者，存储位置和边的端点信息相关。

上述两种做法，各有利弊（其实这要看做什么事情，什么评价指标）。最抽象和广泛的评价指标无非是速度和存储空间。先从空间角度来分析。
如果我们的结构固定。例如，图中有且仅有一个唯一的圈，且任意顶点均在圈上，显然这不是hamilton图，准确说，等于可循环的窗口队列。那么结构存储法自然最优。
因为我们为结构保存额外的信息最小，特别是N固定的情况下。
如果我们的边是动态的。也即结构是动态的。那么边存在标记法和二元关联存储标记法，则要考虑存储空间利用率的问题。
假设我们已知系统规模最大支持N个顶点，和相互之间的边。令N的位宽（需要描述最大N的二进制位）为m。则下面不等式成立时，边存在标记法更优，反之则

二元关联存储标记法更优。

对于一般抽象的图，上述 的信息并不是很明确。但对于平面图，就有一定的指导意义。平面图中，边最多的无非是极大平面图。通过欧拉公式可以得出
所有顶点的度不会超过顶点的6倍。则我们有 而 。因此，很容易判断出，n > 1时就有 因此，二元关联存储标记法更优。
我们看下非平面图中，边数目最多的情况，也即极大图。则很显然， 。此时m > 8 则一定用边存在标记法更好。m 在计算机里我们可以认为
至少是8.一个byte嘛。那么也仅在 小于256的顶点下，两者效果相当。

图用什么方式存储，需要充分考虑客户需求中隐含的提示和约束。也需要考虑存储介质自身的特性。例如外部磁性存储介质（区别于掉电丢失的介质），片内存储介质（SOC内高速存储访问介质），片外存储介质等。

下面考虑计算性能，实质是访问费用的方面：

从历史的工程设计来看，有理由认为，更多情况下，高密集的计算集中在局部数据中。因此，我们使用在算法中，使用什么存储方式，需要考虑片内存储介质的特性。
假设，片内存储为32Kbytes。则我们需要考虑如何令满足客户需求的数据结构，能在32kbytes中有效承载足够的计算任务分配。
原则上，应该以片内存储的空间为基础，--> 确定出二元关联存储标记法的信息承载量 --->根据客户需求中，关于边和顶点的比例关系，--->决定，是否替换为边标记法实现。
以上是对存储容量和承载信息角度来分析。

从实际数据索引和存储迁移角度，还存在一个问题。地址或索引的解析成本。

有一点是肯定的。任何存储介质上，存储的关于顶点或边的索引信息，均为逻辑信息，这些逻辑是针对图本身的。而不是存储逻辑，更不谈实际存储的物理地址信息。例如，我们假设使用指针的方式建立图的索引，指针指向的内容是内存的逻辑地址，但这个逻辑地址是针对逻辑地址空间的。如果简单的将这些信息写入磁盘，再次读入时，由于逻辑地址空间的变化，导致这些指针的实际数据失效。除非始终能保证逻辑地址空间是不变的。

这样矛盾，来源于图本身的逻辑，和存储逻辑之间是完全两个胡不相关的逻辑。

为了解决上述问题，对实际数据的索引或寻址，则必然存在间接索引或间接寻址的工作。正常的做法是索引（图自身信息）和存储地址（计算机的存储信息）剥离。而修正的优化手段是，在进入片内存储介质时，可以考虑，对索引和存储地址的关联转换。以实现计算过程中，地址访问的直接获取。如果这种转换是由硬件设备快速独立的实现就再好不过了。不过通用计算机上，并不现实。特定设备上的开发，由不能作为原理性设计具备广泛存在的意义。因此，图方面的工程原理性设计阶段，需要回避这类问题。

简单的总结，

1、根据客户的需求分析，决策图的基本性质，是否存在固化结构？以选择是否使用“结构存储法”。

2、如果无法使用结构存储法，则需要判断顶点和边的关系，接近平面图特性的时候，采用二元关联存储标记法更优。反之使用边存在标记法。

3、而所有存储信息，均针对图本身，而不针对存储结构。特别是原理性设计阶段。因此要回避诸如使用指针索引作为图结构描述的做法。

转载于: