Ecco come eseguire la ricerca utilizzando una ricerca in ampiezza e nel percorso più breve, utilizzando JOIN. Non c'è magia in questo algoritmo, poiché stiamo usando MySQL per trovare la nostra risposta e non stiamo incorporando alcun algoritmo di ricerca di fantasia che utilizzi alcun tipo di euristica o ottimizzazione.
La mia tabella "amici" ha relazioni unidirezionali, quindi abbiamo duplicati nel senso che sono archiviati sia "da 1 a 2" che "da 2 a 1". Sto anche escludendo is_active poiché l'implementazione sarà ovvia:
Ecco i dati:
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
Abbiamo selezionato il membro 1 e stiamo chiedendo se 1 amico con 7, un amico di un amico, ecc. Un conteggio di 0 significa no e un conteggio di 1 significa sì.
SELECT COUNT(*)
FROM friends f1
WHERE f1.member_id = 1
AND f1.friend_id = 7
Se no, allora sono amici di un amico?
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
Se no, allora amico di un amico di un amico?
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
E così via...
La terza query troverebbe il percorso "da 1 a 2", "da 2 a 6" e "da 6 a 7", restituendo il conteggio di 1.
Ogni query diventa più costosa (a causa del maggior numero di join), quindi potresti voler limitare la ricerca a un certo punto. Una cosa interessante è che questa ricerca funziona da entrambe le estremità verso il centro, che è una semplice ottimizzazione suggerita per le ricerche sul percorso più breve.
Ecco come trovare i consigli di amici comuni per il membro 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
