N分離度訪談problm

最近有人問了一個關於採訪的有趣問題。N分離度訪談problm

例如， A是B朋友，B是C朋友，C是D朋友，d是E朋友，E是F的朋友。所以我們可以說，A知道F。

顯然你不能有效地使用BFS或其他標準遍歷技術來解決這個問題。問題是 - 如何將數據結構存儲在數據庫中以及如何快速執行此搜索。

我沒有找出答案，也許有人有一個想法？

2017-09-02 silent-box

我*猜*'是'的概率約爲99.99999％，所以也許你可以硬編碼'返回是'，但我會等待看到答案。 – alain

[挑戰，如何實現六度分離算法？]的可能重複（https://stackoverflow.com/questions/2076715/challenge-how-to-implement-an-algorithm-for-six-degree-分離） – sascha

@RoryDaulton不，對不起。修正了 –

BFS有什麼問題？

從第一個節點執行BFS的三個步驟，通過標記1標記可訪問的用戶。它需要10^9個步驟。

從第二個節點執行BFS的三個步驟，通過標記2標記可訪問的用戶。如果我們符合標記1 - 賓果。

2017-09-02 17:42:13 MBo

如果您不再擴展已標記的節點（用戶數爲10^6），則需要少於10^6個步驟。 –

@RalfKleberhoff，頂點數達到'pow（10,6）'，但邊數達到'pow（10,9）'。 –

如何將數據存儲爲100萬x100萬個矩陣A其中A [i] [j]是從用戶i到達用戶j的最小步數。然後你可以幾乎立即查詢它。但更新更昂貴。

2017-09-02 19:26:34 algrid

回答