两个用户之间的连接

我运行我自己的网站，人们有能力拥有朋友。这是我如何存储友谊：两个用户之间的连接

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

的想法是找到尽可能

的唯一途径这两个之间的快速链接我可以想到的是创造一个巨大的循环与大量的循环和类似的东西，可能会更好，更高效。

来源

2013-03-12 Nikola

听起来像旅行商的变化？ – KevinDTimm 2013-03-12 17:23:38

这是不平凡的。看看[图论]（http://en.wikipedia.org/wiki/Graph_theory）。 – engineerC 2013-03-12 17:30:59

你在友谊表中大概有多少条目？图表的密度是多少，即大多数人有几个朋友，或大多数人有几百个朋友？是否需要找到绝对最短路径，或者任何路径都可以？你是否想找到路径，不管它有多长，或者你可以停止，例如，最多5个链接？ id1'总是小于'id2'吗？ – mellamokb 2013-03-12 18:18:32

最短的友谊路径通常通过使用称为双向搜索的算法找到。主要想法是将友谊网络视为无向图，在这里寻找2个节点之间的最短路径。该算法同时从两个节点开始搜索，发现已知节点的邻居节点。当已知节点的两个表面首先重叠时，找到最短路径。

请注意，某些特殊情况需要处理，例如其中一个人在图上的“孤岛”，这样的节点集未连接到其他节点（想想没有任何社区与外界的关系）

底线它是一个不太大的while循环。

来源

2013-03-12 18:45:30 sw0rdf1sh

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

来源

2013-08-09 03:13:12

RDBMS不擅长做这样的事情。

你需要的是一个graph db，我强烈建议Neo4j，这是流行和开源。

来源

2013-08-09 03:23:08 adamsmith

我想先尝试的是广度优先搜索。

请注意，以下代码无法修改，因为我没有检查过语法错误。如你所见，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-09 11:02:57 sba

这将与重量为1的边缘。有一个sample code来计算在一个社交网络中的两个朋友之间的连接在PHP

来源

2013-12-31 08:49:29 kb0000

两个用户之间的连接

回答

相关问题