9

我经营自己的网站，人们可以在其中结交朋友。这就是我存储友谊的方式：

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

我们的想法是在这两者之间找到尽可能快的联系

我能想到的唯一方法是创建一个巨大的大循环，其中包含很多循环和类似的东西，这可能会更好、更高效。

4

5 回答 5

3

RDBMS 不擅长做这样的事情。

你需要的是一个图形数据库，我强烈推荐Neo4j，它很流行并且是开源的。

于 2013-08-09T03:23:08.207 回答
1

通常使用一种称为双向搜索的算法来找到最短的友谊路径。主要思想是将友谊网络视为无向图，在其中您正在寻找 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和friends（f2 的好友树）。您将扩展较短的列表，同时在另一个列表中寻找匹配项。但是，您无法欺骗复杂性，因此您必须将迭代限制保持在非常低的水平，除非您喜欢破坏服务器的声音。

于 2013-08-09T11:02:57.600 回答
0

最好在两个方向上进行广度优先搜索，即从有问题的两个人开始，当您找到连接或达到指定的深度限制时停止此过程。这个想法也是为了首先接触更受欢迎的人（在执行 BFS 时）

于 2013-08-09T03:13:12.720 回答
0

这将使用权重为 1 的边。有一个示例代码可以计算 PHP 社交网络中 2 个朋友之间的连接

于 2013-12-31T08:49:29.913 回答