9

私は自分のウェブサイトを運営していて、そこで人々は友達を持つことができます。これが私が友情を保存する方法です：

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

基本的に、ユーザーID1はユーザーID2とID3の友達であり、ユーザー2は友達のユーザーID4です。

私が取得しようとしているのは、たとえば、1と4がどのように接続されているかです。現在はそのようなものです：

1 -> 2 -> 4

それが約4から3の間であれば、次のようになります。

4 -> 2 -> 1 -> 3

アイデアは、これら2つの間の可能な限り迅速なリンクを見つけることです

私が考えることができる唯一の方法は、たくさんのループやそのようなもので大規模な大きなループを作成することです。これはおそらくより良く、より効率的になる可能性があります。

4

5 に答える 5

3

RDBMS は、このようなことを行うのが得意ではありません。

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

于 2013-08-09T03:23:08.207 に答える
1

最短の友情経路は通常、双方向探索と呼ばれるアルゴリズムを使用して見つけられます。主なアイデアは、友情のネットワークを無向グラフとして見て、2 つのノード間の最短経路を探すことです。この前述のアルゴリズムは、両方のノードから同時に検索を開始し、既知のノードの隣接ノードを検出します。既知のノードの 2 つのサーフェスが最初に重なり合うと、最短パスが見つかります。

誰かがグラフの「島」にいる場合、他のノードに接続されていないノード セットなど、特定の特殊なケースを処理する必要があることに注意してください (外部に関係のないコミュニティを考えてください)。世界）

要するに、それはそれほど大きくない while ループです。

于 2013-03-12T18:45:30.307 に答える
1

私が最初に試すのは、幅優先検索です。

次のコードは、構文エラーをチェックしていないため、変更しないと機能しないことに注意してください。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おもちゃのデータベース以外の場合は、2 つのリストとfriends(フレンドのツリーから f2)を保持する双方向検索を行う必要があります。他のリストで一致を探しながら、短いリストを拡張します。ただし、複雑さをだますことはできないため、サーバーを破壊する音が気に入らない限り、反復の制限を非常に低く保つ必要があります。

于 2013-08-09T11:02:57.600 に答える
0

これは、エッジの重みが 1 の場合です。PHP のソーシャル ネットワークで 2 人の友人間のつながりを計算するサンプル コードがあります。

于 2013-12-31T08:49:29.913 に答える