2人のユーザーの接続

Question

私は自分のウェブサイトを運営しています。 これは私が友情を保存する方法です：

id1 | id2 
1 | 2 
1 | 3 
2 | 4 

基本的にはユーザID 1は、ユーザID 2とID 3とユーザ2と友人である私が取得しようとしているどのような友人のユーザID 4.

がどのようになっています例えば、1と4が接続されています。現在はそのようなものだ：

1 -> 2 -> 4 

それは4と3の間のことだ場合、それは次のようになります。

4 -> 2 -> 1 -> 3 

アイデアは、これら2

可能な限り唯一の方法の間のような迅速なリンクを見つけることです私は、ループがたくさんある大規模な大規模なループを作成し、それがおそらくより効率的になるようなものを考えています。

Answer 1

通常、最短の友人関係のパスは、双方向検索と呼ばれるアルゴリズムを使用して検索されます。主なアイデアは、あなたが2つのノード間の最短経路を探している無向グラフとして友情のネットワークを見ることです。このアルゴリズムは、両方のノードから同時に探索を開始し、既知のものの近傍ノードを発見する。既知のノードの2つのサーフェスが最初に重複する場合、最短パスが見つかる。

他のノードに接続されていないノードの集合など、ある人がグラフの「島」にいるときなど、特定の特殊ケースを処理する必要があることに注意してください

ボトムラインあまりにも大きいwhileループです。

Answer 2

両方の方向、つまり問題の両方の個人から幅優先探索を行い、接続を見つけたり、指定された深さの制限に達すると、このプロセスを停止することをお勧めします。 アイデアは、より一般的な個人に最初に到達することです（BFSを実行中）

Answer 3

RDBMSはこのようなことをするのは良くありません。

必要なものはgraph dbです。人気がありオープンソースであるNeo4jを強くお勧めします。

Answer 4

最初に試してみるのは幅優先検索です。

構文エラーもチェックされていないため、次のコードは修正なしでは機能しません。 query（）関数は、表示されているようにエントリのリストを返す必要があります。それはあなたにアイデアを与えることを意図しています。

/* Return one of the shortest friendship paths from f1 to f2. Returns false when 
* path is longer than limit or no path exists. 
* PROTOTYPE FIX IT YOURSELF 
*/ 
function friend_path($f1, $f2, $limit) { 
    $friended = array($f1 => false); // The tree of friendships leading to f1 
    $discovered_friends = array($f1); // List of friends to examine next 
    while($limit-- > 0) { 
     $interesting_friends = $discovered_friends; 
     $discovered_friends = array(); 
     foreach(query(" 
      SELECT id1 AS friender, id2 AS friendee 
      FROM friendships 
      WHERE id1 in (".join(',', $interesting_friends).") 
      ") as $discovered_link 
     ) { 
      $friendee = $discovered_link['friendee']; 
      $friender = $discovered_link['friender']; 
      if (!isset($friended[$friendee])) { 
       $discovered_friends []= $friendee; 
       $friended[$friendee] = $friender; 
       if ($friendee == $f2) { 
        return friend_path_track($friended, $friendee, $track); 
       } 
      } 
     } 
     if (count($discovered_friends) < 1) return false; 
    } 
    return false; 
} 

function friend_path_track($friended, $friendee, $track) { 
    $track []= $friendee; 
    if ($friended[$friendee]) === false) return array_reverse($track); 
    return friend_path_track($friended, $friended[$friendee], $track); 
} 

このコードは、簡単にするために最適化されています。玩具のデータベース以外は、friendedとfriendsの2つのリスト（f2の友人のツリー）を保持する双方向検索を実行する必要があります。他のリストで一致するものを探しながら、短いリストを拡張します。しかし、複雑さを犠牲にすることはできません。したがって、反復の上限を非常に低く抑えなければならないので、サーバを壊すような音が聞こえなくなります。

Answer 5

これは、1の重みを持つエッジになります。sample codeは、ソーシャルネットワーク内の2人の友人の接続をPHPで計算するためのものです