热门问题
时间线
聊天
视角

圖 (數據結構)

計算機科學中的抽象資料結構 来自维基百科,自由的百科全书

图 (数据结构)
Remove ads

計算機科學中,(英語:graph)是一種抽象數據類型,用於實現數學圖論無向圖有向圖的概念。

Thumb
一個有3個節點和3條有向圖

圖的數據結構包含一個有限(可能是可變的)的集合作為節點集合,以及一個無序對(對應無向圖)或有序對(對應有向圖)的集合作為(有向圖中也稱作)的集合。節點可以是圖結構的一部分,也可以是用整數下標或引用表示的外部實體。

圖的數據結構還可能包含和每條邊相關聯的數值(edge value),例如一個標號或一個數值(即權重,weight;表示花費、容量、長度等)。

操作

圖數據結構G支持的基本操作通常包括:[1]

  • adjacent(G, x, y):查看是否存在從節點xy的邊;
  • neighbors(G, x):列出所有從x出發的邊的另一個頂點y
  • add_vertex(G, x):如果不存在,將節點x添加進圖;
  • remove_vertex(G, x):如果存在,從圖中移除節點x
  • add_edge(G, x, y):如果不存在,添加一條從節點xy的邊;
  • remove_edge(G, x, y):如果存在,從圖中移除從節點xy的邊;
  • get_vertex_value(G, x):返回節點x上的值;
  • set_vertex_value(G, x, v):將節點x上的值賦為v

如果該數據結構支持和邊關聯的數值,則通常也支持下列操作[1]

  • get_edge_value(G, x, y):返回邊(x, y)上的值;
  • set_edge_value(G, x, y, v):將邊(x, y)上的值賦為v
Remove ads

圖的常見數據結構

鄰接表[2][3]
節點存儲為記錄對象,且為每個節點創建一個列表。這些列表可以按節點存儲其餘的信息;例如,若每條邊也是一個對象,則將邊存儲到邊起點的列表上,並將邊的終點存儲在邊這個的對象本身。
鄰接矩陣[4][5]
一個二維矩陣,其中行與列分別表示邊的起點和終點。頂點上的值存儲在外部。矩陣中可以存儲邊的值。
關聯矩陣英語incidence matrix[6]
一個二維矩陣,行表示頂點,列表示邊。矩陣中的數值用於標識頂點和邊的關係(是起點、是終點、不在這條邊上等)。

下表給出了在圖上進行各種操作的複雜度。其中,用|V|表示節點數量,|E|表示邊的數量。同時假設存儲的信息是邊上對應的值,如果沒有對應值則存儲∞。

更多信息 , ...

鄰接表在稀疏圖英語sparse graph上比較有效率。鄰接矩陣則常在圖比較稠密的時候使用,判斷標準一般為邊的數量|E |接近於節點的數量的平方|V |2;鄰接矩陣也在查找兩節點鄰接情況較為頻繁時使用。[9][10]

其它表示和存儲圖的數據結構還包括鏈式前向星十字鍊表鄰接多重表英語adjacency multilist等。

Remove ads

並行計算

圖問題的並行計算主要存在如下幾種困難:處理大量的數據、求解非常規的問題、數據不分散、數據存取對計算的比例很高等。[11][12]面對這些困難,並行計算中圖的表示和存儲方式很重要。如果選取了不合適的表示方式,可能帶來不必要的通訊花費,進而影響算法的可擴展性。在本節中,並行計算的共享分布式英語distributed memory存儲模型都在考慮之列。

共享存儲

共享存儲模型下,圖的表示和非並行計算中的場景是相同的,[13],因為在此模型下,對圖表示(如鄰接表)的並行讀取操作效率已經足夠高了。

分布式存儲

分布式存儲英語distributed memory模型下,通常會採用劃分英語graph partition點集個集合的方式,其中是並行處理器的數量。隨後,這些點集劃分及相連的邊按照標號分配給每個並行處理器。每個處理器存儲原圖的一個子圖,而那些兩個頂點分屬兩個子圖的邊則需額外特殊處理。在分布式圖算法中,處理這樣的邊往往意味着處理器之間的通訊。[13]

圖的劃分需要謹慎地在降低通訊複雜度和使劃分均勻之間取捨。[14]但圖劃分本身就是NP難問題。因此,實踐中會使用啟發式方法。

Remove ads

圖的壓縮存儲

機器學習社會網絡分析等領域中,有時會處理數萬億條邊的圖。圖的壓縮存儲可以減少存取和內存壓力。霍夫曼編碼等一些數據壓縮的常見方法是可行的。同時,鄰接表、鄰接矩陣等也有專門的壓縮存儲方法以提高效率。[15]

參見

參考資料

Loading content...

外部連結

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads