Zde je návod, jak provést hledání pomocí hledání nejkratší cesty na šířku a pomocí JOIN. V tomto algoritmu není žádná magie, protože k nalezení odpovědi používáme MySQL a nezahrnujeme žádný luxusní vyhledávací algoritmus, který používá jakýkoli druh heuristiky nebo optimalizace.
Moje tabulka 'přátel' má jednosměrné vztahy, takže máme duplikáty v tom smyslu, že jsou uloženy '1 to 2' a '2 to 1'. Vylučuji také is_active, protože implementace bude zřejmá:
Zde jsou data:
member_id friend_id
1 2
1 3
1 4
2 1
2 3
2 5
2 6
3 2
3 1
4 1
5 2
6 2
6 7
7 6
7 8
8 7
Vybrali jsme člena 1 a ptáme se, zda je 1 přítel se 7, přítel přítele atd.? Počet 0 znamená ne a počet 1 znamená ano.
SELECT COUNT(*)
FROM friends f1
WHERE f1.member_id = 1
AND f1.friend_id = 7
Pokud ne, jsou to přátelé přítele?
SELECT COUNT(*)
FROM friends f1
JOIN friends f2
ON f2.member_id = f1.friend_id
WHERE f1.member_id = 1
AND f2.friend_id = 7
Pokud ne, pak přítel přítele přítele?
SELECT COUNT(*)
FROM friends f1
JOIN friends f2
ON f2.member_id = f1.friend_id
JOIN friends f3
ON f3.member_id = f2.friend_id
WHERE f1.member_id = 1
AND f3.friend_id = 7
A tak dále...
Třetí dotaz by našel cestu „1 až 2“, „2 až 6“ a „6 až 7“, přičemž by vrátil počet 1.
Každý dotaz se prodraží (kvůli většímu počtu spojení), takže možná budete chtít hledání v určitém okamžiku omezit. Skvělá věc je, že toto vyhledávání funguje z obou konců směrem ke středu, což je jednoduchá optimalizace navržená pro hledání nejkratší cesty.
Zde je návod, jak najít doporučení pro společné přátele pro člena 1:
SELECT f2.friend_id
FROM friends f1
JOIN friends f2
ON f2.member_id = f1.friend_id
LEFT JOIN friends f3
ON f3.member_id = f1.member_id
AND f3.friend_id = f2.friend_id
WHERE f1.member_id = 1
AND f2.friend_id <> f1.member_id // Not ourself
AND f3.friend_id IS NULL // Not already a friend