Berikut ini cara melakukan pencarian menggunakan pencarian jalur terpendek pertama, menggunakan GABUNG. Tidak ada keajaiban dalam algoritme ini, karena kami menggunakan MySQL untuk menemukan jawaban kami, dan kami tidak menggabungkan algoritme penelusuran mewah apa pun yang menggunakan heuristik atau pengoptimalan apa pun.
Tabel 'teman' saya memiliki hubungan searah, jadi kami memiliki duplikat dalam arti bahwa '1 ke 2' dan '2 ke 1' disimpan. Saya juga mengecualikan is_active karena implementasinya akan jelas:
Berikut datanya:
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
Kami memiliki anggota 1 yang dipilih, dan kami bertanya apakah 1 teman dengan 7, teman dari teman, dll? Hitungan 0 berarti tidak, dan hitungan 1 berarti ya.
SELECT COUNT(*)
FROM friends f1
WHERE f1.member_id = 1
AND f1.friend_id = 7
Jika tidak, apakah mereka teman dari teman?
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
Jika tidak, lalu teman dari teman dari teman?
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
Dan seterusnya...
Kueri ketiga akan menemukan jalur '1 hingga 2', '2 hingga 6', dan '6 hingga 7', mengembalikan hitungan 1.
Setiap kueri menjadi lebih mahal (karena jumlah gabungan yang lebih besar), jadi Anda mungkin ingin membatasi pencarian di beberapa titik. Satu hal yang keren adalah bahwa pencarian ini bekerja dari kedua ujung ke tengah, yang merupakan salah satu pengoptimalan sederhana yang disarankan untuk pencarian jalur terpendek.
Berikut cara menemukan rekomendasi teman bersama untuk anggota 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
