一種改進的圖存儲結(jié)構(gòu)的實現(xiàn)及性能分析

王海文 羅明山

（百色學(xué)院，廣西 百色 533000）

一種改進的圖存儲結(jié)構(gòu)的實現(xiàn)及性能分析

王海文 羅明山

（百色學(xué)院，廣西 百色 533000）

文章分析了圖的經(jīng)典存儲結(jié)構(gòu)，提出了一種利用三元組和哈希表結(jié)合的方法來改進圖的存儲結(jié)構(gòu)。通過算法性能分析和比較，得出用三元組和哈希表結(jié)合存儲的圖結(jié)構(gòu)能夠有效的提高圖的存儲結(jié)構(gòu)的存儲效率的結(jié)論。

數(shù)據(jù)結(jié)構(gòu)；圖；三元組；哈希表

1 引言

圖是一種強有力的問題抽象的工具，已經(jīng)被廣泛應(yīng)用于計算科學(xué)、運籌學(xué)、信息論、控制論等領(lǐng)域。隨著應(yīng)用科學(xué)的不斷發(fā)展，圖在科學(xué)研究和現(xiàn)實問題求解中起著重要的作用[1]。在日趨龐大的海量數(shù)據(jù)處理中，探索圖結(jié)構(gòu)新的存儲方式以提高數(shù)據(jù)處理效率顯得尤為必要。

2 圖的經(jīng)典存儲結(jié)構(gòu)及效率問題

圖是一種聚合的數(shù)據(jù)結(jié)構(gòu)，由存儲定點的數(shù)據(jù)結(jié)構(gòu)V和存儲頂點的數(shù)據(jù)結(jié)構(gòu)E族和而成，其定義格式為：

其中，V={x|x∈某個數(shù)據(jù)元素集合}

圖的經(jīng)典存儲結(jié)構(gòu)中，頂點V通常采用順序表或單鏈表存儲，邊E則往往采用鄰接矩陣或鄰接鏈表。分析不難發(fā)現(xiàn)，用線性表存儲圖的邊和用鄰接矩陣或鄰接鏈表存儲邊的信息，都有不盡人意之處：

（1）頂點操作效率低。頂點的操作主要表現(xiàn)為存取和插入刪除操作。順序存儲有利于存取操作，但不利于插入和刪除；鏈式存儲有利于插入和刪除操作，但不利于存取操作。因此，無論采用順序存儲還是采用鏈式存儲，對頂點的操作的效率都是不理想的。

（2）邊操作效率低。對于采用鄰接矩陣存儲邊信息的圖，具有n個頂點和e條邊的有向圖，需要(n×n)的鄰接矩陣，存儲效率只有 e/(n×n) ，空間利用率低；當(dāng)插入或刪除頂點時，鄰接矩陣將由 n×n變成(n+1)×(n+1)或(n-1)×(n-1)，矩陣中的數(shù)據(jù)幾乎被重寫一遍，效率為O(n2)；而訪問邊信息時，廣度優(yōu)先和深度優(yōu)先遍歷的效率均為O(n2)[2]。

對于采用鄰接鏈表存儲的圖，鏈表通常采用仿真指針。進行頂點插入和刪除操作時，由于仿真指針變化而引起大量的指針信息修改，操作效率低。

（3）與關(guān)系數(shù)據(jù)庫映像不一致。關(guān)系數(shù)據(jù)庫采用二維表表示實體及實體之間的聯(lián)系（外鍵是對實體之間聯(lián)系的補充）。從邏輯上看都屬于線性關(guān)系。而鄰接矩陣和鄰接鏈表均為非線性結(jié)構(gòu)，不宜直接在關(guān)系數(shù)據(jù)庫中存儲。要使圖的相關(guān)信息能在關(guān)系數(shù)據(jù)庫中進行存儲，必須進行格式轉(zhuǎn)換。

3 圖的三元組存儲結(jié)構(gòu)

數(shù)據(jù)的存儲結(jié)構(gòu)是影響算法效率的關(guān)鍵。要改進圖的算法效率，需要改進圖的存儲結(jié)構(gòu)。

3.1 哈希表與頂點的存儲

哈希表是一種高效的數(shù)據(jù)管理方法，它通過對數(shù)據(jù)的關(guān)鍵字k進行哈希函數(shù)h(k) 計算決定數(shù)據(jù)的存儲位置，其效率由哈希函數(shù)的構(gòu)造方法和哈希沖突的處理方法決定。當(dāng)哈希函數(shù)選取得當(dāng)?shù)臅r候，哈希表的存取、插入和刪除效率均可以達到O(1)。因此，哈希表是一種比順序結(jié)構(gòu)和鏈式結(jié)構(gòu)更具效率數(shù)據(jù)結(jié)構(gòu)。

采用哈希表作為圖的頂點的數(shù)據(jù)結(jié)構(gòu)，可使圖關(guān)于頂點的操作的效率由O(n)提高到O(1)。

3.2 三元組與邊的存儲

N元組是描述事務(wù)和問題的重要方法。圖的一條邊，用三元組可描述為E（Ks，Ke，w），其中Ks為邊的起始結(jié)點的關(guān)鍵字，Ke為邊的終結(jié)結(jié)點的關(guān)鍵字，w邊的權(quán)值。該三元組的抽象數(shù)據(jù)類型定義為：

三元組是對頂點之間關(guān)系（邊）信息的高度抽象。以三元組為結(jié)點，使用線性表來存儲，將圖的非線性結(jié)構(gòu)變?yōu)榫€性結(jié)構(gòu)，操作效率將得到大大改善。

3.3 圖的三元組的存儲結(jié)構(gòu)的效率分析

圖的三元組的存儲結(jié)構(gòu)主要是采用哈希表和三元組改進圖的存儲性能，其數(shù)據(jù)結(jié)構(gòu)定義如下：

由于哈希表存儲，頂點的存取、插入和刪除操作的時間效率均為O(1)。

由于采用三元組，邊的數(shù)據(jù)結(jié)構(gòu)由非線性結(jié)構(gòu)轉(zhuǎn)變?yōu)榫€性結(jié)構(gòu)，edgesList是一個具有e個結(jié)點(e條邊)的線性表，其插入、刪除和訪問操作的時間復(fù)雜度為O(e)。

對于深度優(yōu)先遍歷，每個頂點搜索第 1個鄰接點或E(k1,k2)的下一條鄰接邊時，平均需要訪問e個結(jié)點，而遍歷完n個頂點共需要訪問e×n次，所以，深度優(yōu)先遍歷的算法復(fù)雜度為 O(e×n)。理同深度優(yōu)先遍歷，廣度優(yōu)先遍歷算法的時間復(fù)雜度亦為O(e×n)。

根據(jù)以上分析，結(jié)合文獻[1]和文獻[2]，可得出如表 1所示的算法信息分析比較表。

表1 三種圖結(jié)構(gòu)操作性能比較

4 結(jié)論

文章分析了圖在經(jīng)典數(shù)據(jù)結(jié)構(gòu)中以鄰接矩陣和鄰接鏈表實現(xiàn)時的不足之處，提出了一種利用三元組和哈希表存儲處理圖的存儲結(jié)構(gòu)的方法。通過比較分析算法的性能，證明圖的三元組存儲結(jié)構(gòu)是一種更具效率的數(shù)據(jù)結(jié)構(gòu)。

圖的三元組存儲有效地將圖的非線性關(guān)系轉(zhuǎn)換為線性關(guān)系，并使用與關(guān)系數(shù)據(jù)庫一致的“關(guān)鍵字”作為邊的起點和終點信息，使圖和關(guān)系數(shù)據(jù)庫更方便地實現(xiàn)對接。基于這一點，圖的三元組存儲結(jié)構(gòu)比圖的經(jīng)典存儲存儲結(jié)構(gòu)更具有實用價值。

[1] 嚴慰敏.數(shù)據(jù)結(jié)構(gòu)(c語言)[M].北京:清華大學(xué)出版社.

[2] 朱戰(zhàn)立.數(shù)據(jù)結(jié)構(gòu)—java語言描述[M].北京:清華大學(xué)出版社,2005-12:207-217.

[3] 羅明山.圖的數(shù)據(jù)庫存儲與轉(zhuǎn)換[J].電腦開發(fā)與應(yīng)用, 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－），男，湖北麻城人，百色學(xué)院數(shù)學(xué)與計算機信息工程系助教，研究方向為軟件開發(fā)技術(shù)、計算機網(wǎng)絡(luò)；羅明山（1979－），男，廣西隆林人，百色學(xué)院數(shù)學(xué)與計算機信息工程系講師，研究生，研究方向為計算機軟件與理論、并行計算。