So führen Sie die Suche mit einer Breitensuche auf dem kürzesten Weg mithilfe von JOIN durch. Dieser Algorithmus ist nicht magisch, da wir MySQL verwenden, um unsere Antwort zu finden, und wir verwenden keinen ausgefallenen Suchalgorithmus, der irgendeine Art von Heuristik oder Optimierung verwendet.
Meine „Freunde“-Tabelle hat unidirektionale Beziehungen, also haben wir Duplikate in dem Sinne, dass sowohl „1 zu 2“ als auch „2 zu 1“ gespeichert werden. Ich schließe auch is_active aus, da die Implementierung offensichtlich sein wird:
Hier sind die Daten:
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
Wir haben Mitglied 1 ausgewählt und fragen, ob 1 mit 7 befreundet ist, ein Freund eines Freundes usw.? Eine Zählung von 0 bedeutet nein und eine Zählung von 1 bedeutet ja.
SELECT COUNT(*)
FROM friends f1
WHERE f1.member_id = 1
AND f1.friend_id = 7
Wenn nein, sind sie dann Freunde eines Freundes?
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
Wenn nein, dann Freund eines Freundes eines Freundes?
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
Und so weiter...
Die dritte Abfrage würde den Pfad „1 bis 2“, „2 bis 6“ und „6 bis 7“ finden und den Zählerstand 1 zurückgeben.
Jede Abfrage wird teurer (aufgrund der größeren Anzahl von Joins), sodass Sie die Suche möglicherweise irgendwann einschränken möchten. Eine coole Sache ist, dass diese Suche von beiden Enden zur Mitte hin funktioniert, was eine einfache Optimierung ist, die für Suchen auf dem kürzesten Weg vorgeschlagen wird.
So finden Sie die gemeinsamen Freundschaftsempfehlungen für Mitglied 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
