一种改进的图存储结构的实现及性能分析

王海文 罗明山

（百色学院，广西 百色 533000）

一种改进的图存储结构的实现及性能分析

王海文 罗明山

（百色学院，广西 百色 533000）

文章分析了图的经典存储结构，提出了一种利用三元组和哈希表结合的方法来改进图的存储结构。通过算法性能分析和比较，得出用三元组和哈希表结合存储的图结构能够有效的提高图的存储结构的存储效率的结论。

数据结构；图；三元组；哈希表

1 引言

图是一种强有力的问题抽象的工具，已经被广泛应用于计算科学、运筹学、信息论、控制论等领域。随着应用科学的不断发展，图在科学研究和现实问题求解中起着重要的作用[1]。在日趋庞大的海量数据处理中，探索图结构新的存储方式以提高数据处理效率显得尤为必要。

2 图的经典存储结构及效率问题

图是一种聚合的数据结构，由存储定点的数据结构V和存储顶点的数据结构E族和而成，其定义格式为：

其中，V={x|x∈某个数据元素集合}

图的经典存储结构中，顶点V通常采用顺序表或单链表存储，边E则往往采用邻接矩阵或邻接链表。分析不难发现，用线性表存储图的边和用邻接矩阵或邻接链表存储边的信息，都有不尽人意之处：

（1）顶点操作效率低。顶点的操作主要表现为存取和插入删除操作。顺序存储有利于存取操作，但不利于插入和删除；链式存储有利于插入和删除操作，但不利于存取操作。因此，无论采用顺序存储还是采用链式存储，对顶点的操作的效率都是不理想的。

（2）边操作效率低。对于采用邻接矩阵存储边信息的图，具有n个顶点和e条边的有向图，需要(n×n)的邻接矩阵，存储效率只有 e/(n×n) ，空间利用率低；当插入或删除顶点时，邻接矩阵将由 n×n变成(n+1)×(n+1)或(n-1)×(n-1)，矩阵中的数据几乎被重写一遍，效率为O(n2)；而访问边信息时，广度优先和深度优先遍历的效率均为O(n2)[2]。

对于采用邻接链表存储的图，链表通常采用仿真指针。进行顶点插入和删除操作时，由于仿真指针变化而引起大量的指针信息修改，操作效率低。

（3）与关系数据库映像不一致。关系数据库采用二维表表示实体及实体之间的联系（外键是对实体之间联系的补充）。从逻辑上看都属于线性关系。而邻接矩阵和邻接链表均为非线性结构，不宜直接在关系数据库中存储。要使图的相关信息能在关系数据库中进行存储，必须进行格式转换。

3 图的三元组存储结构

数据的存储结构是影响算法效率的关键。要改进图的算法效率，需要改进图的存储结构。

3.1 哈希表与顶点的存储

哈希表是一种高效的数据管理方法，它通过对数据的关键字k进行哈希函数h(k) 计算决定数据的存储位置，其效率由哈希函数的构造方法和哈希冲突的处理方法决定。当哈希函数选取得当的时候，哈希表的存取、插入和删除效率均可以达到O(1)。因此，哈希表是一种比顺序结构和链式结构更具效率数据结构。

采用哈希表作为图的顶点的数据结构，可使图关于顶点的操作的效率由O(n)提高到O(1)。

3.2 三元组与边的存储

N元组是描述事务和问题的重要方法。图的一条边，用三元组可描述为E（Ks，Ke，w），其中Ks为边的起始结点的关键字，Ke为边的终结结点的关键字，w边的权值。该三元组的抽象数据类型定义为：

三元组是对顶点之间关系（边）信息的高度抽象。以三元组为结点，使用线性表来存储，将图的非线性结构变为线性结构，操作效率将得到大大改善。

3.3 图的三元组的存储结构的效率分析

图的三元组的存储结构主要是采用哈希表和三元组改进图的存储性能，其数据结构定义如下：

由于哈希表存储，顶点的存取、插入和删除操作的时间效率均为O(1)。

由于采用三元组，边的数据结构由非线性结构转变为线性结构，edgesList是一个具有e个结点(e条边)的线性表，其插入、删除和访问操作的时间复杂度为O(e)。

对于深度优先遍历，每个顶点搜索第 1个邻接点或E(k1,k2)的下一条邻接边时，平均需要访问e个结点，而遍历完n个顶点共需要访问e×n次，所以，深度优先遍历的算法复杂度为 O(e×n)。理同深度优先遍历，广度优先遍历算法的时间复杂度亦为O(e×n)。

根据以上分析，结合文献[1]和文献[2]，可得出如表 1所示的算法信息分析比较表。

表1 三种图结构操作性能比较

4 结论

文章分析了图在经典数据结构中以邻接矩阵和邻接链表实现时的不足之处，提出了一种利用三元组和哈希表存储处理图的存储结构的方法。通过比较分析算法的性能，证明图的三元组存储结构是一种更具效率的数据结构。

图的三元组存储有效地将图的非线性关系转换为线性关系，并使用与关系数据库一致的“关键字”作为边的起点和终点信息，使图和关系数据库更方便地实现对接。基于这一点，图的三元组存储结构比图的经典存储存储结构更具有实用价值。

[1] 严慰敏.数据结构(c语言)[M].北京:清华大学出版社.

[2] 朱战立.数据结构—java语言描述[M].北京:清华大学出版社,2005-12:207-217.

[3] 罗明山.图的数据库存储与转换[J].电脑开发与应用, 2009年11月第11期总183期.

ACHIEVEMENT AND PERFORMANCE ANALYSIS OF AN IMPROVED STORAGE STRUCTURE OF GRAPH

Analyzing the classic storage structure of graph, proposed a method that combination of Triples and Hash tables to improve the storage structure of the graph. Through analysis on algorithm performance, obtained a conclusion that this way, drawn in the pager, can effectively improve the storage efficiency of storage structure of graph.

data structure; graph; Triples ; Hash table

TP181

A

1008-1151(2012)05-0006-02

2012-04-15

王海文（1981－），男，湖北麻城人，百色学院数学与计算机信息工程系助教，研究方向为软件开发技术、计算机网络；罗明山（1979－），男，广西隆林人，百色学院数学与计算机信息工程系讲师，研究生，研究方向为计算机软件与理论、并行计算。