1樓：杜傳贏
這是乙個非常有趣的問題, 現實工程中也被人實現較多, 其實不是那麼的難!
最關鍵的優化點其實是:
1. 雙向廣搜, 把六度直接降為三度, 計算量一下就減化非常非常的多了, 雖然其實還是指數級的複雜度.
2. 快取二度/三度好友的結果, 用空間換時間
1. 能否快速獲取任意兩個使用者的好友關係度數（最大為六）
能, 假設最壞的情況, 即兩個使用者剛好是六度, (如果是三度, 四度, 更容易算出來):
一度好友是 25個, 那三度好友最多是: 15625 個好友, 由於現實資料一定有很多的交集, 可能最終是 8000, 甚至不到5000個好友. 兩個使用者都先算出他的 5000 個三度好友, 然後相交一下, 看有無交集?
如果有交集, 那就是六度好友(其實也可能是四度, 甚至二度好友, 所以要先把這種情況算出來), 如果沒有, 那一定不是六度好友.
如何求三度好友? 對於 1kw 使用者來說, 其實預計算快取三度的結果也挺簡單的, 資料量沒有多大.
5000個使用者id, 壓縮壓縮10K肯定能搞定, 乘以1kw, 也就是不到100GB的資料.
按使用者去做hash儲存, 大多數據用不到, 快取命中率能很高, 真這個資料規模的話, 單機已經基本能夠做到了準實時的查詢了(50ms以內返回).
預處理的時候, 確實需要一些時間.
1a. 是否能夠將度數最大為六的限制任意提高？如計算得到某兩個使用者的關係度數是 100，兩個完全不連通的使用者關係度數可定義為正無窮。
這個我的理解是不可能的, 好在這是指數的增長, 所以現實中, 超過 6度, 到 8度, 甚至更高的幾乎完全沒有意義, 幾乎一定互聯! 允許一定誤差的話, 不計算, 直接告訴互聯就OK了!
特殊場景, 或者刻意構造資料是有可能的, 但是類似孤島資料, 鏈式資料... 這個可以特殊處理, 一般線上系統就是捨棄這種精度了.
2. 能否儲存或快速獲取任意兩個使用者之間的最短路徑？
能, 類似 1. 的解法, 還是雙向廣搜, 記路徑, 儲存空間會適當增加, 或者得到中間人後, 重新算到每個中間人的最短路徑, 得到最終的最短路徑. 計算時間和儲存空間肯定要增加不少.
但是量級應該不變!
3. 當使用者好友關係發生變化時，是否能增量更新之前的計算結果？抑或全域性重新計算的效率比增量更新的效率更高？
計算機學生，現在學習資料結構和演算法設計，不知道應該怎樣學習
你的唐長老 要看你是學純計算機的還是通訊物聯網這些 計算機學習在世界上有兩種論調，自上而下和自下而上。我們國家的大學大多數都是自下而上學習，先學習基礎演算法，編譯原理，計算機原理，彙編文法這些，然後再學習實踐學科 你要學資料結構，大概說明你是大一大二的學生。資料結構是一定要從演算法開始的。演算法最基...
自學資料結構 計算機網路 資料庫 演算法設計，有什麼比較推薦的書籍？
堯堯 資料結構 C語言版 嚴蔚敏主編的那版 演算法很細緻，思路清晰，排版也很規範，對於初學者來說很不錯，即使C語言沒有學好也看得懂 Database Design for Mere Mortals A Hands On Guide to Relational Database Design 3rd ...
怎麼高效得學習資料結構和演算法？
岳陽樓妓 多練，找一些練習題，多寫才會有效果，光靠記效率是極其低下的，最好練習，做的多了就理解了。或者一遍練習，一遍看看各種演算法和資料結構，邊看邊練。 3cpj 掌握一門計算機語言是前提。如果沒有基礎的計算機語言知識，很難說實現演算法了，不但要掌握，而且還要熟悉，譬如 c 語言作為入門的經典語言，...