Voici comment effectuer la recherche à l'aide d'une recherche par chemin le plus court en largeur, à l'aide de JOIN. Il n'y a pas de magie dans cet algorithme, car nous utilisons MySQL pour trouver notre réponse, et nous n'incorporons aucun algorithme de recherche fantaisiste qui utilise un quelconque type d'heuristique ou d'optimisation.
Ma table 'amis' a des relations unidirectionnelles, nous avons donc des doublons dans le sens où '1 à 2' et '2 à 1' sont stockés. J'exclus également is_active car la mise en œuvre sera évidente :
Voici les données :
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
Nous avons sélectionné le membre 1, et nous demandons 1 amis avec 7, un ami d'un ami, etc. Un compte de 0 signifie non et un compte de 1 signifie oui.
SELECT COUNT(*)
FROM friends f1
WHERE f1.member_id = 1
AND f1.friend_id = 7
Si non, alors sont-ils amis d'un ami ?
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 non, alors ami d'un ami d'un ami ?
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
Et ainsi de suite...
La troisième requête trouverait le chemin '1 à 2', '2 à 6' et '6 à 7', renvoyant le nombre de 1.
Chaque requête devient plus coûteuse (en raison du plus grand nombre de jointures), vous pouvez donc limiter la recherche à un moment donné. Une chose intéressante est que cette recherche fonctionne des deux extrémités vers le milieu, ce qui est une optimisation simple suggérée pour les recherches de chemin le plus court.
Voici comment trouver ces recommandations d'amis communs pour le membre 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
