首先,我不是想创建一个社交网络,Facebook足够大！ (漫画)
我选择了这个问题作为例子,因为它完全符合我正在做的事情.
想象一下,我在MySQL中有一个用户表和一个带有“朋友请求”的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!
}
该功能的问题是它可以搜索整个数据库,而不会找到最大的圈子或最佳匹配.
我会谈论“边缘”连接的“节点”,而不是“人”是“朋友”.循环从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和length进行跟踪.它需要空间…但是,这是您为图形搜索周期的内存成本.它可以简化,取决于你想做什么;详细说明.
顺便说一下,我假设图形是无向的 – 换句话说,一个从一个节点到另一个节点的边缘都是双向的.在连接中,具有最低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的新链.
然后当节点被删除时,您应该取出相应的链和循环 – 链表将足够大.