一.What-圖的概念：如下就是一個(gè)圖(非線性表數(shù)據(jù)結(jié)構(gòu))
圖的分類：無(wú)向圖(微信-不允許單向關(guān)注)、有向圖(微博-允許單向關(guān)注)、帶權(quán)圖(QQ-親密度)
圖相關(guān)概念：
- 頂點(diǎn)：圖中的元素叫作頂點(diǎn)
- 邊：一個(gè)頂點(diǎn)可以與任意其他頂點(diǎn)建立連接關(guān)系，這種建立的關(guān)系叫作邊
- 度：跟頂點(diǎn)相連接的邊的條數(shù)叫做度
- 入度和出度：有向圖中把度分為入度(表示有多少條邊指向這個(gè)頂點(diǎn))和出度(表示有多少條邊是以這個(gè)頂點(diǎn)為起點(diǎn)指向其他頂點(diǎn))
- 帶權(quán)圖：在帶權(quán)圖中每條邊都有一個(gè)權(quán)重
二.圖的存儲(chǔ)
- 鄰接矩陣
- 鄰接矩陣的底層依賴一個(gè)二維數(shù)組。
- 對(duì)于無(wú)向圖來(lái)說(shuō)，如果頂點(diǎn) i 與頂點(diǎn) j 之間有邊，我們就將 A[i][j] 和 A[j][i] 標(biāo)記為 1；
- 對(duì)于有向圖來(lái)說(shuō)，如果頂點(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)重
- 缺點(diǎn)：浪費(fèi)存儲(chǔ)空間
- 鄰接表存儲(chǔ)方法
- 無(wú)向圖A[i][j] 等于 1，那 A[j][i] 也肯定等于 1，只需要存儲(chǔ)一個(gè)
- 稀疏圖-頂點(diǎn)很多，但每個(gè)頂點(diǎn)的邊并不多
- 優(yōu)點(diǎn)：
存儲(chǔ)方式簡(jiǎn)單、直接，因?yàn)榛跀?shù)組，所以在獲取兩個(gè)頂點(diǎn)的關(guān)系時(shí)，就非常高效方便計(jì)算。這是因?yàn)?，用鄰接矩陣的方式存?chǔ)圖，可以將很多圖的運(yùn)算轉(zhuǎn)換成矩陣之間的運(yùn)算
存儲(chǔ)方式： - 每個(gè)頂點(diǎn)對(duì)應(yīng)一條鏈表，鏈表中存儲(chǔ)的是與這個(gè)頂點(diǎn)相連接的其他頂點(diǎn)
- 有向圖的鄰接表存儲(chǔ)方式，每個(gè)頂點(diǎn)對(duì)應(yīng)的鏈表里面，存儲(chǔ)的是指向的頂點(diǎn)
- 無(wú)向圖來(lái)說(shuō)，每個(gè)頂點(diǎn)的鏈表中存儲(chǔ)的，是跟這個(gè)頂點(diǎn)有邊相連的頂點(diǎn)
- 優(yōu)點(diǎn)：存儲(chǔ)節(jié)省空間
- 缺點(diǎn)：查找比較耗時(shí)間(鄰接表中鏈表的存儲(chǔ)方式對(duì)緩存不友好，所以比起鄰接矩陣，在鄰接表中查詢兩個(gè)頂點(diǎn)之間的關(guān)系就沒(méi)那么高效)
- 可以將鄰接表中的鏈表改成平衡二叉查找樹(shù)(紅黑樹(shù))等動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)(跳表、散列表等)，這樣就可以更加快速地查找兩個(gè)頂點(diǎn)之間是否存在邊了。
- 可以將鏈表改成有序動(dòng)態(tài)數(shù)組，可以通過(guò)二分查找的方法來(lái)快速定位兩個(gè)頂點(diǎn)之間否是存在邊
- 逆鄰接表：每個(gè)頂點(diǎn)的鏈表中，存儲(chǔ)的是指向這個(gè)頂點(diǎn)的頂點(diǎn)
思考
如何存儲(chǔ)微博、微信等社交網(wǎng)絡(luò)中的好友關(guān)系？支持如下幾個(gè)操作：
判斷用戶 A 是否關(guān)注了用戶 B；
判斷用戶 A 是否是用戶 B 的粉絲；
用戶 A 關(guān)注用戶 B；用戶 A 取消關(guān)注用戶 B；
根據(jù)用戶名稱的首字母排序，分頁(yè)獲取用戶的粉絲列表；
根據(jù)用戶名稱的首字母排序，分頁(yè)獲取用戶的關(guān)注列表如何找出社交網(wǎng)絡(luò)中的三度好友關(guān)系？（可能認(rèn)識(shí)的人）
廣度優(yōu)先搜索（BFS）
深度優(yōu)先搜索（DFS）
迷宮可以抽象成圖，走迷宮可以抽象成搜索算法，你能具體講講，如何將迷宮抽象成一個(gè)圖嗎？或者換個(gè)說(shuō)法，如何在計(jì)算機(jī)中存儲(chǔ)一個(gè)迷宮？
A、IDA等搜索算法
