基本概念
- 圖是一種非線性的數(shù)據(jù)結(jié)構(gòu)洁仗，相比樹來說层皱，更加復(fù)雜。
- 圖的元素叫頂點(diǎn)赠潦，樹的元素叫節(jié)點(diǎn)叫胖。
- 度：頂點(diǎn)相連的邊的條數(shù)叫度。
圖的分類有無向圖她奥、有向圖瓮增、帶權(quán)圖
無向圖
邊沒有方向的圖員無向圖。無向圖中的頂點(diǎn)相連的邊的條數(shù)叫度哩俭。例如微信上的好友關(guān)系绷跑。
有向圖
邊有方向的圖叫有向圖。有向圖中分為入度和出度携茂。入度指終點(diǎn)為此頂點(diǎn)的邊的條數(shù)；出度指始點(diǎn)為此頂點(diǎn)的邊的條數(shù)诅岩。例如微博上的關(guān)注和粉絲關(guān)系讳苦。
帶權(quán)圖
每條邊都有一個(gè)權(quán)重的圖叫帶權(quán)圖带膜。例如QQ上與好友的親密度。
圖的存儲(chǔ)方式
圖有兩種存儲(chǔ)方式鸳谜，分別為鄰接矩陣和鄰接表膝藕。
鄰接矩陣
通過二維數(shù)組來保存圖的邊。其中無向圖(i, j)和(j, i)設(shè)置為1咐扭，有向圖設(shè)置帶方向的邊芭挽，比如(i, j)設(shè)置為1，帶權(quán)圖把值設(shè)置為權(quán)重蝗肪。
- 好處：存儲(chǔ)簡單袜爪、訪問方便、方便計(jì)算
- 壞處：浪費(fèi)空間
鄰接表
每個(gè)頂點(diǎn)存儲(chǔ)一個(gè)鏈表薛闪，存儲(chǔ)的是這個(gè)頂點(diǎn)的相連的頂點(diǎn)辛馆。跟之前學(xué)過的散列表很像。每個(gè)頂點(diǎn)存儲(chǔ)的是指向的頂點(diǎn)豁延，無論是有向圖還是無向圖昙篙。
- 好處：節(jié)省空間
- 壞處：操作耗時(shí)
優(yōu)化：通過對(duì)鏈表進(jìn)行改造，使用跳表诱咏、散列表苔可、平衡二叉樹、紅黑樹等數(shù)據(jù)結(jié)構(gòu)來優(yōu)化袋狞。
案例分析
如何存儲(chǔ)微博焚辅、微信等社交網(wǎng)絡(luò)中的好友關(guān)系？
針對(duì)微博用戶關(guān)系硕并，假設(shè)我們需要支持下面這樣幾個(gè)操作：
- 判斷用戶A是否關(guān)注了用戶B法焰；
- 判斷用戶A是否是用戶B的粉絲；
- 用戶A關(guān)注用戶B倔毙；
- 用戶A取消關(guān)注用戶B埃仪；
- 根據(jù)用戶名稱的首字母排序，分頁獲取用戶的粉絲列表陕赃；
- 根據(jù)用戶名稱的首字母排序卵蛉，分頁獲取用戶的關(guān)注列表。
技術(shù)選型思路：
1么库、確定存儲(chǔ)方式
因?yàn)樯缃魂P(guān)系是稀疏的傻丝，選擇鄰接表。
因?yàn)榧纫榭搓P(guān)注的诉儒，還要查看粉絲葡缰，因此除了使用鄰接表，還需要逆鄰接表。
2滤愕、存儲(chǔ)方式的底層數(shù)據(jù)結(jié)構(gòu)
需要按用戶名稱首字母排序，并且要優(yōu)化操作性能怜校，因此選擇跳表改造基礎(chǔ)的鄰接表间影，并且還有很重要的一點(diǎn)，跳表本身的數(shù)據(jù)是有序的茄茁。
3魂贬、確定數(shù)據(jù)規(guī)模
因?yàn)閱蝹€(gè)計(jì)算機(jī)資源是有限的，例如內(nèi)存裙顽、磁盤空間付燥。數(shù)據(jù)規(guī)模對(duì)存儲(chǔ)方案有很大的影響。
對(duì)于小規(guī)模數(shù)據(jù)锦庸，幾十萬數(shù)據(jù)量机蔗，將鄰接表直接保存到內(nèi)存中。
對(duì)于大規(guī)模數(shù)據(jù)甘萧，數(shù)以億計(jì)萝嘁，就需要存儲(chǔ)在多臺(tái)服務(wù)器上⊙锞恚可使用哈希算法來計(jì)算用戶存儲(chǔ)在哪臺(tái)服務(wù)器上牙言。
另外，也可存儲(chǔ)在磁盤上怪得。磁盤相對(duì)于內(nèi)存來說咱枉，空間更大。比如數(shù)據(jù)庫文件就是存儲(chǔ)在磁盤上徒恋，可通過索引優(yōu)化查詢效率蚕断。
