Połączenie między dwoma użytkownikami

Question

Prowadzę własną stronę internetową, na której ludzie mają możliwość zawierania znajomości. ten sposób przechowywać przyjaźnie:

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

Zasadniczo id użytkownika 1 znajomość z identyfikatorem użytkownika 2 i 3 oraz id użytkownika 2 jest id znajomi użytkownika 4.

Co Próbuję dostać się jak na przykład są połączone 1 i 4. Obecnie jest tak:

1 -> 2 -> 4 

Jeśli chodzi o między 4 i 3 byłoby:

4 -> 2 -> 1 -> 3 

Chodzi o to, aby znaleźć jak szybki związek pomiędzy tymi dwoma, jak to możliwe

Jedynym sposobem Mogę myśleć o tworzeniu ogromnej, wielkiej pętli z dużą ilością pętli i podobnych rzeczy, które prawdopodobnie mogą być lepsze i bardziej wydajne.

Answer 1

Najkrótszą ścieżkę przyjaźni zwykle można znaleźć za pomocą algorytmu zwanego wyszukiwarką dwukierunkową. Główną ideą jest spojrzenie na sieć znajomych jako graf nieukierunkowany, w którym poszukujesz najkrótszej ścieżki pomiędzy 2 węzłami. Wspomniany algorytm rozpoczyna wyszukiwanie z obu węzłów w tym samym czasie, odkrywając sąsiednie węzły już znanych. Kiedy dwie powierzchnie znanych węzłów najpierw zachodzą na siebie, wówczas znajduje się najkrótsza ścieżka.

Należy pamiętać, że niektóre szczególne przypadki wymagają obsługi, na przykład gdy jedna z osób znajduje się na "wyspie" na wykresie, taki zestaw węzłów, który nie jest połączony z innymi węzłami (należy myśleć o społeczności bez związek z tym światem zewnętrznym)

Dolna linia to niezbyt duża pętla while.

Answer 2

Najlepiej jest wykonać jednoetapowe wyszukiwanie w obu kierunkach, tj. Od obu osób i zatrzymać ten proces po znalezieniu połączenia lub osiągnięciu określonego limitu głębokości. Chodzi o to, aby najpierw dotrzeć do bardziej popularnych osób (podczas wykonywania BFS).

Answer 3

RDBMS nie jest dobry w robieniu takich rzeczy.

To, czego potrzebujesz, to graph db, i zdecydowanie polecam Neo4j, która jest popularna i otwarta.

Answer 4

To, co chciałbym najpierw wypróbować, to pierwsze wyszukiwanie.

Należy pamiętać, że poniższy kod nie będzie działał bez modyfikacji, ponieważ nie sprawdziłem nawet błędów składni. Funkcja query() powinna zwrócić listę wpisów, jak widzisz. Ma na celu dać ci pomysł.

/* 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); 
} 

Ten kod został zoptymalizowany pod kątem prostoty. W przypadku jakichkolwiek baz danych zabawek powinieneś robić dwukierunkowe wyszukiwanie, w którym trzymasz dwie listy: friended i friends (drzewo znajomych na f2). Rozszerzałbyś listę, która jest krótsza, podczas szukania meczu na drugiej liście. Nie można jednak oszukać złożoności, więc będziesz musiał utrzymać limit iteracji na bardzo niskie poziomy, które podoba ci się dźwięk serwerów.

Answer 5

Byłoby to z krawędziami o wadze 1.Jest sample code do obliczenia połączenia między 2 przyjaciółmi w sieci społecznościowej w PHP