ソーシャルネットワークフォローモデルのBFSまたはDFS

Question

ソーシャルネットワークのフォロワーグラフを実装しようとしています。

要件はこのように、わかりやすくするために、グラフの各ユーザーuのプロファイルを正の整数値P [u]で表すと仮定できます。私はデートサービスを提供するように求められています。目標は、各ユーザーuのための良い出会いパートナーを生成することです。その人物が、u（もしあれば）とまったく同じプロファイルを持つ連鎖を通じて到達可能な場合、パートナーは良いです。

これはグラフのトラバーサルの問題です。私はそれを自分で実装できますが、ここでの質問は、DFSを使用するかBFSを使用する方が良いかどうかがわかりません。

Answer 1

複雑さの観点から、両方のアルゴリズムはO（V + E）で実行されます。メモリ空間の観点からは、DFSはBFSより優れています。だから、もしあなたが記憶を気にしていれば、DFSはあなたのために良いでしょう。メモリを脇に置くだけで、あなたにとって最適なアルゴリズムを知ることができます。たとえば、他のパートナーと比較してユーザーに近い優れたパートナーを好むかもしれません。ユーザーには多くの良いパートナーがいるかもしれません。あなたが最初に近い良いパートナーを探したいならば、BFSはあなたのためにそれを行います。それ以外の場合は、違いはありません。以下の例を見ると、DFS（1）は1の良いパートナーとして8または7を返します.BFS（1）を実行している間は、最初に1の良いパートナーとして7を得ます。