查找從另一個人到另一個人所需的人數

以下是問題設置：您在社交網絡上選擇一個隨機人（A），例如Facebook，然後在Facebook上選擇另一個隨機人（B）。假設你有權訪問每個人的朋友列表，你如何找到從A到達B所需的人數。例如： A是C，V，T，Y，Z的朋友 C是朋友與V，T，A，L V與C，A，Q，W的朋友 T與C，A，Q，B的朋友Y和Z也有一些朋友。答案是這樣的，因爲A-> T-> B查找從另一個人到另一個人所需的人數

什麼是解決這個問題的有效方法？

來源

2016-03-15 mantrarush

取決於您的數據表示。一般情況下，你想找到從A到B的最短路徑。 –

沒錯，除了我覺得在列表中找到一個鏈接之前，通過列表遍歷列表很繁瑣。 – mantrarush

Dijkstra算法。您只需要將關係表示爲圖形。

來源

2016-03-15 15:38:31 MasterID

BFS會更簡單快捷。 – beaker

甚至可能是雙向BFS，因爲朋友圖中的分支因子通常非常高。 –

查找從另一個人到另一個人所需的人數

回答

相關問題