Pythonのソーシャルグラフの幅優先検索の使用

Question

私は幅優先検索、dfs、A *などの使い方についてstackoverflowに関する多くの質問を読んできましたが、質問は最適な使い方と方法現実的なシミュレーションのグラフでそれを実装する。例えば。

は、私には、次のように検索アルゴリズムがうまくいくようです、あなたは、Twitter/Facebookの/いくつかのソーシャルネットワーキングサイトのソーシャルグラフを持って考えてみましょう：

ユーザーAは10人の友人を持っていた場合、それらの一つは、2人の友人を持っていましたもう1つ3.検索では、ユーザーAの友だちが誰だったかを最初に把握し、10人のユーザーのそれぞれにどこに友達がいるかを調べなければなりません。私にはこれはbfsのようですか？

しかし、アルゴリズムを実装する方法はわかりません。

おかげで、私の2セントで

Answer 1

、あなたはそれはあなたが、それが一度だけ、各ノードに当たるとして使用しているもののアルゴリズム全体の多くを重要ではありません全体のグラフをトラバースしようとしている場合。これは、あなたの専門用語を使用すると、およそ歩行を話している技術的にflawed-されることを意味、私はちょうど全体のグラフを横断する

をしようとしている

：これは、あなたが注意したときに何を言っていることのようですグラフではなく、検索グラフです。あなたが実際に特に何かを検索しようとしているのでない限り、あなたはその質問では全く言及していないようです。言ったことで

、FacebookやTwitterはあなたがそれらを歩いてどのように影響を持っている非常に異なるグラフ構造です：

1. Facebookは基本的に無向グラフです。 XがYと友人である場合、YはXと友人である必要があります（または関係、または関係など）。

2. Twitterは基本的に有向グラフです。 XがYに続く場合、YはXをたどる必要はありません。

これらの問題は、グラフウォーキングアルゴリズムに大きな影響を与えます。あなたがすべてのノードを訪問したいだけなら、かなり正直なことに、グラフが必要なのでしょうか？なぜそれらのすべてを繰り返すだけではないのですか？明らかに、あなたはあなたが実際にしているどのように処理するためにnodeGeneratorの内部を調整する必要があると思い

def nodeGenerator(MY_DATA) 
    for node in MY_DATA: 
     yield node 

：あなたが反復可能であるいくつかのデータ構造MY_DATA内のすべてのノードがある場合は、ちょうどこのようなジェネレータ式を持つことができますノードにアクセスする。これにより、ほとんどのグラフ構造はノードイテレータを実装します。

for node in nodeGenerator(MY_DATA): 
    (Do something here) 

たぶん私はちょうどここに質問のポイントを逃していたが、現在では、あなたが検索せ​​ずに検索アルゴリズムについての質問を提起しました：次に、あなただけを経由して、あなたは物事をやりたいイテレータをいつでも作成することができます問題。 No Free Lunchの最適化と検索の性質により、検索アルゴリズムの価値は、調査しようとしている検索の問題に完全に依存します。

同じデータセットであっても同じです。結局のところ、文字Dで始まる名前の人を探していたら、誰もアルファベット順に並べ替えてバイナリ検索をするのがよいでしょう。代わりに、ケビン・ベーコンから誰もが分離の程度を見出そうとしているならば、あなたはベーコン氏から始まり、彼と彼が知っているすべての人を知っているすべての人を再帰的に反復することを望みます。これらはFacebookやTwitterでできることですが、実際にはアルゴリズムを推薦する方法はありません。したがって、あなたが何も知らない場合は、すべての人をリストとして反復するだけです。それは他の何かと同じくらい良いことです。最適化したい場合は、計算をキャッシュします。

Answer 2

私は約300人の友人がfacebookにおり、私の友人の中には平均300人の友達がいます。あなたがグラフを作ろうとすれば、それは巨大になるでしょう。私が間違っているなら、私を訂正してください。 。このシナリオでは、BFSは大量に終了するでしょうか？

おかげで J