樹和圖都是非線性表數(shù)據(jù)結(jié)構(gòu)继蜡，之前我們已經(jīng)學(xué)習(xí)了樹，現(xiàn)在我們就學(xué)習(xí)更為復(fù)雜的圖逛腿。

圖的概念

在這里主要介紹圖的類型以及關(guān)于圖的一些概念稀并，我們會使用 微信、微博单默、QQ 三種社交軟件的社交關(guān)系作為例子幫助理解稻轨。

無向圖、頂點(diǎn)雕凹、邊、度

在樹中政冻，我們將元素成為節(jié)點(diǎn)枚抵，而在圖中的元素，我們叫做頂點(diǎn)（vertex）明场。兩個(gè)頂點(diǎn)之間建立的連接關(guān)系叫做邊（edge）汽摹。一個(gè)頂點(diǎn)有多少邊與之相連，成為一個(gè)頂點(diǎn)的度（degree）苦锨。你可以看一下下面的圖：

無向圖.jpg

有向圖

微信中以互相添加好友作為建立邊的原則吉捶，這種社交關(guān)系在微博中不太一樣：在微博中，允許用戶單向關(guān)注皆尔，即用戶 A 關(guān)注了 B呐舔，而 B 不一定要關(guān)注 A。我們?nèi)绾斡脠D來表示這種關(guān)系呢慷蠕？

我們需要為圖引入“方向”的概念珊拼。

如果 A 關(guān)注了 B ，我們就在圖中畫一條從 A 到 B 的帶剪頭的邊流炕，使用剪頭表示邊的方向澎现。我們把這種有方向邊的圖稱作有向圖。類似的浪感，我們將之前講到的例子稱為無向圖昔头。

有向圖.jpg

帶權(quán)圖

QQ中的社交關(guān)系要更復(fù)雜一些，在兩個(gè)QQ好友之間會有“親密度”這樣一個(gè)功能峻堰。它不僅維護(hù)了兩個(gè)用戶之間的好友關(guān)系讹开，還記錄了兩個(gè)用戶之間的親密度。

在圖中捐名，我們使用帶權(quán)圖表示這種關(guān)系旦万。帶權(quán)圖中，每條邊都有一個(gè)權(quán)重镶蹋，我們可以通過這個(gè)權(quán)重來表示QQ好友之間的親密度：

帶權(quán)圖.jpg

圖的存儲

圖的存儲可以分為兩類：鄰接矩陣 和 鄰接表成艘。

鄰接矩陣（Adjacency Matrix）

圖最直觀的存儲方法是使用鄰接矩陣。

我們用一個(gè)二維數(shù)組記錄各個(gè)頂點(diǎn)之間的邊：

• 無向圖：如果頂點(diǎn) i 與頂點(diǎn) j 之間有邊贺归，就將 A[i][j] 和 A[j][i] 標(biāo)記為 1淆两；
• 有向圖：如果有一個(gè)邊從 i 指向 j ，將A[i][j] 標(biāo)記為 1 拂酣；
• 帶權(quán)圖：在數(shù)組中存儲權(quán)重秋冰。

圖存儲-鄰接矩陣.jpg

鄰接矩陣的優(yōu)點(diǎn)：

• 鄰接矩陣的存儲方式簡單、直接婶熬，可以高效地獲取兩個(gè)頂點(diǎn)之間的關(guān)系剑勾。
• 鄰接矩陣可以方便地使用矩陣之間的計(jì)算埃撵。

鄰接矩陣的缺點(diǎn)：

• 對于無向圖來說，鄰接矩陣是關(guān)于主軸對稱的虽另，這浪費(fèi)了一半的存儲空間暂刘。
• 如果用鄰接矩陣存儲稀疏圖，會非常浪費(fèi)空間洲赵。比如微信有好幾億的用戶鸳惯，但是每個(gè)人的好友并不會很多。如果使用鄰接矩陣存儲叠萍，絕大部分的空間都會被浪費(fèi)掉芝发。

鄰接表（Adjacency List）

我們有另一種存儲圖的方法：使用鏈表記錄邊，也就是使用鄰接表苛谷。

圖存儲-鄰接表.jpg

鄰接表的優(yōu)點(diǎn)：

• 鄰接表存儲比較節(jié)省空間刻炒。
• 我們可以通過對鏈表的升級改造提升鄰接表的性能。例如自沧，將鏈表改造成紅黑樹或跳表坟奥，這樣可以支持快速查找。你甚至可以將鏈表改造成有序動態(tài)數(shù)組拇厢，用二分查找爱谁。（你可真是花哨 (→ . →) ）

鄰接表的缺點(diǎn)：

• 鄰接表的存儲方式對緩存不夠友好。
• 鄰接表比鄰接矩陣更耗時(shí)間孝偎。
• 鄰接表記錄了頂點(diǎn)出度信息访敌，如果要查詢?nèi)攵刃畔ⅲ托枰~外的逆鄰接表衣盾。

應(yīng)用場景

如何存儲微博的好友關(guān)系寺旺？

數(shù)據(jù)結(jié)構(gòu)是為算法服務(wù)的，所以具體選擇哪種存儲方式势决，與期望的操作有關(guān)迅涮。對微博的用戶關(guān)系，假設(shè)我們需要支持下面的操作：

• 判斷用戶 A 是否關(guān)注的 B徽龟。
• A 關(guān)注 B。
• A 取消關(guān)注 B唉地。
• 根據(jù)用戶名稱的首字母排序据悔，分頁獲取用戶的粉絲列表传透。
• 根據(jù)用戶名稱的首字母排序，分頁獲取用戶的關(guān)注列表极颓。

分析和選取

• 社交網(wǎng)絡(luò)是一張稀疏圖朱盐，左移我們使用鄰接表存儲。
• 一張鄰接表只能查詢某個(gè)用戶的關(guān)注列表菠隆，無法查詢他被誰關(guān)注（也就是粉絲列表）兵琳。這里就需要引入逆鄰接表表示某個(gè)用戶被關(guān)注的關(guān)系：
  逆鄰接表.jpg
• 某個(gè) 大V 可能有茫茫多的粉絲，這就對列表的查找性能提出了要求骇径，同時(shí)我們又需要對用戶進(jìn)行分頁展示躯肌，使用跳表替代鏈表是一個(gè)非常好的選擇。
• 微博有龐大的用戶破衔，一臺電腦的內(nèi)存是無法存儲的清女，這需要我們對鄰接表和逆鄰接表進(jìn)行分布存取，具體思路在之前的哈希應(yīng)用中已經(jīng)講過：
  分布式存儲圖.jpg

• 當(dāng)然晰筛，你也可以使用數(shù)據(jù)庫完成存儲：
  圖存儲-數(shù)據(jù)庫存儲.jpg

綜上嫡丙，我們需要使用鄰接表和逆鄰接表作為存儲的基本結(jié)構(gòu)，使用跳表代替鏈表方便查詢读第，使用分布式的思想保存如此龐大的數(shù)據(jù)曙博。（有沒有對這個(gè)分析過程感到神奇？）

小結(jié)

• 理解了幾個(gè)概念：無向圖怜瞒、有向圖父泳、帶權(quán)圖、頂點(diǎn)盼砍、邊尘吗、度、入度浇坐、出度睬捶。
• 學(xué)習(xí)了兩種圖的主要存儲方式：鄰接矩陣 和 鄰接表。
• 鄰接矩陣：查詢效率高近刘，方便矩陣運(yùn)算擒贸。但是特別耗費(fèi)空間。
• 鄰接表：節(jié)省內(nèi)存空間觉渴，但是它的查詢效率較低介劫，不方便查找。針對這個(gè)問題案淋，我們可以對鏈表進(jìn)行改造以適應(yīng)各種需求座韵。

以上就是本節(jié)的內(nèi)容

注：本文章的主要內(nèi)容來自我對極客時(shí)間app的《數(shù)據(jù)結(jié)構(gòu)與算法之美》專欄的總結(jié)，我大量引用了其中的代碼和截圖，如果想要了解具體內(nèi)容誉碴，可以前往極客時(shí)間