A continuación, se explica cómo realizar la búsqueda mediante una búsqueda de ruta más corta y primero en anchura, utilizando JOIN. No hay magia en este algoritmo, ya que estamos usando MySQL para encontrar nuestra respuesta y no estamos incorporando ningún algoritmo de búsqueda sofisticado que use algún tipo de heurística u optimización.
Mi tabla de 'amigos' tiene relaciones unidireccionales, por lo que tenemos duplicados en el sentido de que se almacenan tanto '1 a 2' como '2 a 1'. También excluyo is_active ya que la implementación será obvia:
Aquí están los datos:
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
Hemos seleccionado al miembro 1, y estamos preguntando si 1 es amigo de 7, ¿es amigo de un amigo, etc.? Una cuenta de 0 significa que no, y una cuenta de 1 significa que sí.
SELECT COUNT(*)
FROM friends f1
WHERE f1.member_id = 1
AND f1.friend_id = 7
Si no, ¿entonces es amigo de un amigo?
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
Si no, ¿entonces amigo de un amigo de un amigo?
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
Y así sucesivamente...
La tercera consulta encontraría la ruta '1 a 2', '2 a 6' y '6 a 7', devolviendo la cuenta de 1.
Cada consulta se vuelve más costosa (debido a la mayor cantidad de uniones), por lo que es posible que desee limitar la búsqueda en algún momento. Una cosa interesante es que esta búsqueda funciona desde ambos extremos hacia el medio, que es una optimización simple sugerida para búsquedas de ruta más corta.
Aquí se explica cómo encontrar esas recomendaciones de amigos en común para el miembro 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
