社交網絡的BFS或DFS遵循模型

Question

我試圖實現社交網絡追隨者圖。

要求是這樣的，爲了簡單起見，我們可以假設圖中每個用戶u的概況由一個正整數值P [u]表示。我被要求提供約會服務。目標是爲每個用戶生成一個好的約會合作夥伴。如果可以通過一系列跟隨你的人（如果有的話）完全相同的人來訪問這個人，那麼合作伙伴是很好的。

這是一個圖遍歷問題，我可以自己實現，但這裏的問題是我不確定在這種情況下使用DFS或BFS是否更好？

Answer 1

從複雜性的角度來看，兩種算法都以O（V + E）運行。從內存空間的角度來看，DFS比BFS要好。所以如果你關心記憶，DFS對你會更好。拋開記憶，你只能知道哪些算法最適合你。例如，您可能更喜歡比其他合作伙伴更接近用戶的好合作夥伴。用戶可能有許多好的合作伙伴。所以如果你想找到一個更接近的優秀合作伙伴，BFS會爲你做到這一點。否則，沒有區別。看下面的例子，DFS（1）可能會返回8或7作爲1的良好合作夥伴。在運行BFS（1）時，您將始終獲得7作爲1的良好合作夥伴。