Связь между двумя пользователями

Question

Я управляю своим собственным сайтом, где люди имеют возможность иметь друзей. Это, как хранить дружбу:

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

В основном идентификатор пользователя 1 дружит с идентификатором пользователя 2 и идентификатором 3 и 2 пользователя дружит идентификатор пользователя 4.

Что я пытаюсь получить как , например, соединены 1 и 4. В настоящее время это так:

1 -> 2 -> 4 

Если речь идет о между 4 и 3 было бы:

4 -> 2 -> 1 -> 3 

Идея заключается в том, чтобы найти как можно быстро связь между этими двумя, как это возможно

Единственным способом Я могу думать о создании массивной большой петли с множеством петель и тому подобным, который, вероятно, может быть лучше и эффективнее.

Answer 1

Самый короткий путь дружбы обычно используется с использованием алгоритма, называемого двусторонним поиском. Основная идея - посмотреть на сеть дружеских отношений как неориентированный граф, где вы ищете кратчайший путь между двумя узлами. Этот упомянутый алгоритм начинает поиск с обоих узлов одновременно, обнаруживает соседние узлы уже известных. Когда две поверхности известных узлов сначала перекрываются, чем найден самый короткий путь.

Обратите внимание, что некоторые особые случаи необходимо обрабатывать, например, когда один из людей находится на «острове» на графике, такой набор узлов, который не связан с другими узлами (подумайте о сообществе без отношение к внешнему миру)

Нижняя линия - это не очень большой цикл.

Answer 2

Лучше всего выполнить поиск по ширине в обоих направлениях от обоих особей, о которых идет речь, и остановить этот процесс, когда вы найдете соединение или достигнете указанного предела глубины. Идея также состоит в том, чтобы в первую очередь достичь более популярных людей (при выполнении BFS)

Answer 3

RDBMS не умеет делать такие вещи.

Что вам нужно, это graph db, и я настоятельно рекомендую Neo4j, который является популярным и открытым источником.

Answer 4

Что я хотел бы попробовать первым - это поиск в ширину.

Обратите внимание, что следующий код не будет работать без изменений, поскольку я даже не проверял наличие синтаксических ошибок. Функция 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). Вы расширите список, который будет короче, ища совпадение в другом списке. Вы не можете обмануть сложность, хотя, так что вам нужно будет ограничивать итерации очень низко, чтобы вам нравилось звуковое сопровождение серверов.

Answer 5

Это будет с краями, имеющими вес 1.Есть sample code для расчета соединения между двумя друзьями в социальной сети в PHP