大家好，
首先，我不是想创建一个社交网络，Facebook已经足够大了！（漫画）我选择这个问题作为例子，因为它完全符合我想要做的事情。
想象一下，我在MySQL中有一个users表和一个带有"好友请求"的user_connections表。如果是这样，它将是这样的：
Users Table:
userid username
1 John
2 Amalia
3 Stewie
4 Stuart
5 Ron
6 Harry
7 Joseph
8 Tiago
9 Anselmo
10 Maria
User Connections Table:
userid_request userid_accepted
2 3
7 2
3 4
7 8
5 6
4 5
8 9
4 7
9 10
6 1
10 7
1 2
现在我想找到朋友之间的圈子，创建一个结构数组并将该圈子放在数据库中（没有一个数组可以包含另一个数组已经拥有的相同朋友）。
Return Example:
// First Circle of Friends
Circleid => 1
CircleStructure => Array(
1 => 2,
2 => 3,
3 => 4,
4 => 5,
5 => 6,
6 => 1,
)
// Second Circle of Friends
Circleid => 2
CircleStructure => Array(
7 => 8,
8 => 9,
9 => 10,
10 => 7,
)
我正在尝试一种算法来做到这一点，但我认为这将需要大量的处理时间，因为它会随机搜索数据库，直到它"关闭"一个圆圈。
PS：一个圆的最小结构长度是3个连接，限制是100（所以守护程序不会搜索整个数据库）
编辑：
我想过这样的事情：
function browse_user($userget='random',$users_history=array()){
$user = user::get($userget);
$users_history[] = $user['userid'];
$connections = user::connection::getByUser($user['userid']);
foreach($connections as $connection){
$userid = ($connection['userid_request']!=$user['userid']) ? $connection['userid_request'] : $connection['userid_accepted'];
// Start the circle array
if(in_array($userid,$users_history)) return array($user['userid'] => $userid);
$res = browse_user($userid, $users_history);
if($res!==false){
// Continue the circle array
return $res + array($user['userid'] => $userid);
}
}
return false;
}
while(true){
$res = browse_user();
// Yuppy, friend circle found!
if($res!==false){
user::circle::create($res);
}
// Start from scratch again!
}
这个函数的问题在于它可以搜索整个数据库，而没有找到最大的圆圈或最佳匹配。
对于单个批处理来说，对大型数据集执行此类操作几乎总是一项（太）大的工作。处理大量数据时，应连续构建索引。每次添加"用户"或与另一个"用户"成为"朋友"时，都要进行圆圈测试，并将生成的圆圈存储在索引表中。然后，当一个新的"用户"注册或成为另一个"用户"的"朋友"时，你应该使用你的索引数据库根据旧的圈子来寻找新的圈子。
编辑：
我对这个问题非常感兴趣，所以我做了一个概念验证课程，介绍了boisvert关于如何解决这个问题的想法。我把代码放在GitHub上：https://github.com/alfreddatakillen/Six-Degrees-of-Separation（在这里发布会有点混乱）。
它似乎工作得很好。但是，我还没有用大量数据对其进行测试。我很确定你将不得不优化它，因为它基本上是一种蛮力攻击，存储过程中的每一步......（如果您确实优化或使用代码，如果您将更改推送到 GitHub，我会很高兴 - 我可能想自己在未来的项目中使用它。
：-）
Alfred Godoy的回答非常有用，因为处理应该逐步完成。我将尝试充实一些具体的细节。
与其说"人"是"朋友"，不如说"节点"由"边缘"连接。周期从 3 个增加到 4 个（或 n 到 n+1 个）节点是不正确的。几个不形成循环的边可以被新的边封闭并形成一个新的循环。
因此，相反（或同样）作为循环列表，我们应该维护一个边缘链列表。 例如，假设这个连接表：
userid_request userid_accepted
2 7
3 7
3 8
然后链表应包含以下内容：
chainid start end length
1 2 3 2
1 2 8 3
2 7 8 2
此结构允许您记录和检索任意长度的链，并且给定链的两端，使用 id 和长度跟踪它。它需要空间...但这是在图表中为您搜索周期的内存成本。它可以简化，具体取决于您要做什么;提供详细信息。
顺便说一下，我假设图形是无向的 - 换句话说，从一个节点到另一个节点的边是双向的。在连接中，id最低的节点将始终是"请求"，最高id在"接受"端。
添加新节点时，您希望维护链表并查看新节点是否关闭链循环。它涉及几个查询。我给你一个。
假设在"连接"表中添加了一个新条目：
userid_request userid_accepted
@new_request @new_accepted
您可以使用查询来选择任何此类周期。您已经知道新链接及其两个节点，因此您只在寻找关闭它的链：
select chainid, length
from chain
where (start = @new_request and end = @new_accepted)
or (end = @new_request and start = @new_accepted)
（请注意，由于图形不是定向的，因此您必须查找两个周期配置）。
要维护链表，每次添加边时：
- 查找节点延长的现有链
- 寻找长度为 2 的新链。
然后当节点被删除时，您应该取出相应的链和循环 - 链表将足够大。
您是否正在尝试做类似六度分离
的事情乍一看，这是一个NP-hard问题，因为为了计算每个圆，你必须遍历图中的每个节点才能找到所有可能的圆。我相信没有简单的方法可以做到这一点，而且很可能没有办法实时做到这一点。
因此，您可能应该在作业中执行此类计算，并缓存结果以提高效率。
在我看来，如果我们将这个问题视为图形，每个用户作为一个节点，每个关系作为权重为 1 的边，我们可以使用广度优先搜索从用户 1 中找到最大权重为 6 的所有路径。在每个节点遍历（总权重为 6）上，我们搜索起始节点和当前节点是否共享一条边。如果是这样，我们关闭圆圈。它将从 2 的圆圈开始并继续扩展。如果我们达到权重 6 并且最终节点不与起始节点共享边，我们将丢弃圆。
可能在真实情况下，为了加快速度，您可以尝试为每个用户计算较小的总权重（例如 3），然后尝试加入圆圈以达到 6。
只是一个创建圆圈的想法 - 每次用户尝试查看圆圈时都会加载此函数：
- 查找好友最多的用户 ，但尚未在任何圈子中。
- 循环他所有的朋友，寻找一个拥有最多朋友并且尚未在任何圈子中的
- 以相同的方式循环所有新找到的朋友的朋友，直到循环结束，限制 20？
- 检查找到的最后一个用户 （#20） 是否是第一个用户的好友
- 如果是，则圆圈完成
- 如果不是，请检查是否有任何（#19）的朋友是第一个用户的朋友。
- 如果否，请检查是否有任何（#18）的朋友是第一个用户的朋友。
- 继续向后循环用户，直到某人与第一个用户成为好友
- 圆完结
我知道尝试这个的奇怪方法
我认为对于这种类型的工作，您应该在NOSQL数据库上进行中继，该数据库擅长您正在寻找的内容，可能是像Neo4j这样的图形数据库。