鄰接矩陣存儲(chǔ)方法
圖最直觀的一種存儲(chǔ)方法就是，鄰接矩陣 (Adjacency Matrix)。鄰接矩陣的底層依賴一個(gè)二維數(shù)組瞎颗。
對(duì)于無(wú)向圖來(lái)說桂躏，如果頂點(diǎn) i 和 j 之間有邊，我們就將 A[i][j] 和 A[j][i] 標(biāo)記為 1亏掀；對(duì)于有向圖來(lái)說，如果頂點(diǎn) i 到頂點(diǎn) j 之間，有一條箭頭從頂點(diǎn) i 指向頂點(diǎn) j 的邊纳寂，我們就將 A[i][j] 標(biāo)記為 1。同理泻拦，如果有一條箭頭從頂點(diǎn) j 指向頂點(diǎn) i 的邊毙芜，我們就將 A[j][i] 標(biāo)記為 1。對(duì)于帶權(quán)圖争拐，數(shù)組中存儲(chǔ)的就是相應(yīng)的權(quán)重腋粥。
鄰接矩陣存儲(chǔ)法的優(yōu)點(diǎn)是，直觀架曹，簡(jiǎn)單隘冲，可以利用 CPU 的緩存機(jī)制。缺點(diǎn)是绑雄，浪費(fèi)空間展辞。
對(duì)于無(wú)向圖來(lái)說，一條邊要重復(fù)存儲(chǔ)兩個(gè)位置万牺，浪費(fèi)了一半空間罗珍。對(duì)于稀疏圖來(lái)說，脚粟，很多頂點(diǎn)之間并沒有聯(lián)系覆旱，他們相關(guān)的邊的標(biāo)記位的空間就浪費(fèi)了。
但鄰接矩陣簡(jiǎn)單的存儲(chǔ)方式也使得在此基礎(chǔ)上的算法都實(shí)現(xiàn)起來(lái)比較簡(jiǎn)單核无。比如：
- 獲取兩個(gè)頂點(diǎn)間的關(guān)系扣唱，直接按數(shù)組下標(biāo)就可以獲得，非常迅速。
- 用弗洛伊德算法求最短路徑画舌，只要利用矩陣相乘若干次即可得到結(jié)果堕担。
鄰接表存儲(chǔ)方法
鄰接表 (Adjacency List) 最簡(jiǎn)單的實(shí)現(xiàn)方式如下：
如圖可以看到，每個(gè)頂點(diǎn)對(duì)應(yīng)一條鏈表曲聂，鏈表中存儲(chǔ)的是這個(gè)頂點(diǎn)出發(fā)的邊霹购。
與鄰接矩陣相反，鄰接表存儲(chǔ)起來(lái)比較節(jié)省空間朋腋，但是計(jì)算起來(lái)比較耗時(shí)齐疙。不過有辦法對(duì)鄰接表進(jìn)行優(yōu)化。
常見的鄰接表存儲(chǔ)方式的優(yōu)化操作有：
- 如果鏈表過長(zhǎng)旭咽，可以進(jìn)行“樹化”贞奋。
- 如果有按順序查找某一頂點(diǎn)相關(guān)頂點(diǎn)的需求。比如按拼音首字母分頁(yè)查找微博粉絲列表穷绵，就可以選擇將鏈表改裝成跳表轿塔。
- 也可以將鏈表改裝成動(dòng)態(tài)數(shù)組，這樣就可以合理利用 cpu 的緩存仲墨，也可以應(yīng)用二分查找算法進(jìn)行高效查找勾缭。
- 還可以將鏈表改裝成哈希表，在常數(shù)時(shí)間內(nèi)獲取是否兩個(gè)頂點(diǎn)之間有相關(guān)關(guān)系目养。
如何存儲(chǔ)微博用戶關(guān)系俩由？
數(shù)據(jù)結(jié)構(gòu)是為特定算法服務(wù)的，具體選擇那種儲(chǔ)存方法癌蚁，與期望支持的操作有關(guān)系幻梯。假設(shè)針對(duì)微博用戶關(guān)系，假設(shè)我們需要支持以下操作：
- 判斷用戶 A 是否關(guān)注了用戶 B
- 判斷用戶 A 是否是用戶 B 的粉絲
- 用戶 A 關(guān)注用戶 B
- 用戶 A 取消關(guān)注用戶 B
- 根據(jù)用戶名稱首字母排序努释，分頁(yè)獲取用戶的粉絲列表
- 根據(jù)用戶名稱首字母排序碘梢，分頁(yè)獲取用戶的關(guān)注列表
- 那在存儲(chǔ)方式上，因?yàn)樯缃痪W(wǎng)絡(luò)是一張稀疏圖洽洁，所以我們選擇用鄰接表來(lái)存儲(chǔ)痘系。
- 因?yàn)橐樵冇脩舯魂P(guān)注的列表，僅用鄰接圖是非常浪費(fèi)效率的饿自，所以我們?cè)僭黾右粡埬驵徑訄D汰翠，存儲(chǔ)用戶的被關(guān)注關(guān)系。加快獲取粉絲列表的速度昭雌。
- 基礎(chǔ)的鄰接表查找一個(gè)用戶是否在另一個(gè)用戶的關(guān)注列表中复唤，速度不夠快，所以我們選擇對(duì)鄰接表進(jìn)行優(yōu)化烛卧。
- 因?yàn)橐词鬃帜概判颢@取用戶的關(guān)注列表佛纫，所以我們選擇用跳表來(lái)代替鄰接表中的鏈表妓局。
- 假設(shè)用戶規(guī)模比較大，一臺(tái)機(jī)器裝不下一整個(gè)表呈宇，我們可以用哈希分片的方式在不同的機(jī)器上存儲(chǔ)這個(gè)表好爬。
- 假設(shè)表的大小需要擴(kuò)容，可以把哈希分片方式升級(jí)為一致性哈希分片甥啄。
假設(shè)數(shù)據(jù)需要持久性保存存炮，可以用關(guān)系數(shù)據(jù)庫(kù)保存。并在表上建立索引蜈漓。
假設(shè)數(shù)據(jù)海量穆桂，可以使用專業(yè)的圖數(shù)據(jù)庫(kù)。
