Dưới đây là cách thực hiện tìm kiếm bằng cách sử dụng tìm kiếm theo chiều rộng, ưu tiên đường dẫn ngắn nhất, sử dụng JOIN. Không có phép thuật nào trong thuật toán này, vì chúng tôi đang sử dụng MySQL để tìm câu trả lời của mình và chúng tôi không kết hợp bất kỳ thuật toán tìm kiếm ưa thích nào sử dụng bất kỳ loại heuristics hoặc tối ưu hóa nào.
Bảng 'bạn bè' của tôi có các mối quan hệ một chiều, vì vậy chúng tôi có các bản sao theo nghĩa là cả '1 đến 2' và '2 đến 1' đều được lưu trữ. Tôi cũng loại trừ is_active vì việc triển khai sẽ rõ ràng:
Đây là dữ liệu:
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
Chúng tôi đã chọn thành viên 1, và chúng tôi đang hỏi là 1 người bạn với 7 người, một người bạn của một người bạn, v.v.? Số 0 có nghĩa là không và số 1 có nghĩa là có.
SELECT COUNT(*)
FROM friends f1
WHERE f1.member_id = 1
AND f1.friend_id = 7
Nếu không, thì họ có phải là bạn của một người bạn không?
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
Nếu không, thì bạn của một người bạn của một người bạn?
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
Và như vậy ...
Truy vấn thứ ba sẽ tìm đường dẫn '1 đến 2', '2 đến 6' và '6 đến 7', trả về số lượng là 1.
Mỗi truy vấn trở nên đắt hơn (do số lượng liên kết lớn hơn), vì vậy bạn có thể muốn giới hạn tìm kiếm tại một số điểm. Một điều thú vị là tìm kiếm này hoạt động từ cả hai đầu đến giữa, đây là một cách tối ưu hóa đơn giản được đề xuất cho các tìm kiếm đường dẫn ngắn nhất.
Đây là cách tìm các đề xuất kết bạn chung đó cho thành viên 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
