cách quyết định xem hai người có được kết nối với

Question

Đây là vấn đề:

giả sử hai người được đăng ký trên trang web mạng xã hội, cách quyết định xem họ có được kết nối hay không?

phân tích của tôi (sau khi đọc thêm): thực ra, câu hỏi đang tìm kiếm - đường đi ngắn nhất từ ​​A đến B trong biểu đồ. Tôi nghĩ rằng cả hai thuật toán BFS và Dijkstra đều hoạt động ở đây và độ phức tạp thời gian là giống nhau (O (V + E)) bởi vì nó là đồ thị không có trọng số, vì vậy chúng tôi không thể tận dụng ưu tiên hàng đợi ưu tiên. Vì vậy, một hàng đợi đơn giản có thể giải quyết vấn đề. Nhưng, cả hai đều không giải quyết được vấn đề đó: tìm đường đi giữa chúng.

Bidrectrol phải là giải pháp tốt hơn vào thời điểm này.

Answer 1

Lưu ý: câu trả lời đã được chỉnh sửa.

Bất kỳ phương pháp nào cũng có thể rất chậm. Nếu bạn cần làm điều này nhiều lần, tốt nhất là tìm các thành phần được kết nối của biểu đồ, sau đó tác vụ trở thành hoạt động O (1) tầm thường: nếu hai người ở cùng một thành phần, chúng được kết nối.

Lưu ý rằng việc tìm kiếm các thành phần được kết nối lần đầu tiên có thể chậm, nhưng giữ chúng được cập nhật khi các cạnh/nút mới được thêm vào biểu đồ nhanh.

Có một số phương pháp để tìm các thành phần được kết nối.

Một phương pháp là xây dựng Laplacian của biểu đồ và xem giá trị riêng của nó/giá trị riêng. Số lượng các giá trị riêng của số không cho bạn số lượng các thành phần được kết nối. Các phần tử khác không của các phần tử riêng tương ứng cho các nút thuộc về các thành phần tương ứng.

Một cách khác là dọc theo dòng sau đây:

1. Tạo một bảng chuyển đổi của các nút. Phần tử n của mảng chứa chỉ mục của nút mà nút n chuyển đổi thành.

2. Vòng qua tất cả các cạnh (i,j) trong đồ thị (biểu thị một mối liên hệ giữa i và j):

   • Tính đệ quy mà nút làm i và j chuyển tới căn cứ vào bảng hiện tại. Hãy để chúng tôi biểu thị kết quả theo số k và l. Cập nhật mục nhập k để biến nó thành l. Cập nhật các mục i và j để trỏ tới l.

3. Vòng qua bàn một lần nữa, và cập nhật mỗi mục để chỉ trực tiếp đến nút nó đệ quy chuyển đến.

Bây giờ các nút trong cùng một thành phần được kết nối sẽ có cùng mục nhập trong bảng chuyển đổi. Vì vậy, để kiểm tra xem hai nút được kết nối, chỉ cần kiểm tra xem chúng có chuyển đổi thành cùng một giá trị hay không.

Mỗi khi một nút hoặc cạnh mới được thêm vào biểu đồ, bảng chuyển đổi cần phải được cập nhật, nhưng bản cập nhật này sẽ nhanh hơn nhiều so với tính toán ban đầu của bảng.

Answer 2

Để tìm một con đường giữa hai, bạn nên bắt đầu với một tìm kiếm rộng đầu tiên. Đầu tiên tìm thấy tất cả các nước láng giềng của A, sau đó tìm thấy tất cả các hàng xóm của A, v.v.

Dijkstra's algorithm đá và bạn có thể tăng tốc độ này bằng cách làm việc từ cả hai đầu, tức là tìm hàng xóm của A và hàng xóm của B và so sánh.

Nếu bạn thực hiện tìm kiếm chiều sâu đầu tiên, thì bạn đang theo một đường dẫn tại một thời điểm. Điều này sẽ chậm hơn nhiều.

Answer 3

Tôi nghĩ rằng các tiêu chí thực sự là: có ít nhất N đường dẫn giữa A và B ngắn hơn K sau đó, hoặc A và B được kết nối với nhau. Tôi sẽ đi với K = 3 và N gần 5, tức là có 5 người bạn chung.

Answer 4

Một cách là sử dụng Liên minh Tìm, thêm tất cả các liên kết union(from,to), và nếu find(A) is find(B) là True thì A và B được kết nối. Điều này tránh tìm kiếm đệ quy nhưng nó thực sự tính toán kết nối của tất cả các cặp và không cung cấp cho bạn các đường dẫn kết nối A và B.

Answer 5

Nếu bạn thực hiện dfs để tìm xem liệu hai người có được kết nối trên mạng xã hội hay không thì sẽ mất quá nhiều thời gian!

Bạn đã biết hai người, vì vậy bạn nên sử dụng Bidirectional Search.. Tuy nhiên, tìm kiếm hai chiều đơn giản sẽ không đủ cho một đồ thị lớn như một trang web mạng xã hội. Bạn sẽ phải sử dụng một số chẩn đoán. Trang Wikipedia có một số liên kết đến nó.

Bạn cũng có thể sử dụng A* search. Từ wikipedia: "A * sử dụng tìm kiếm tốt nhất và tìm đường dẫn chi phí thấp nhất từ ​​nút ban đầu cho đến một nút mục tiêu (trong số một hoặc nhiều mục tiêu có thể). "

Chỉnh sửa: Tôi đề xuất A * vì "Độ phức tạp bổ sung khi thực hiện tìm kiếm hai chiều có nghĩa là thuật toán tìm kiếm A * thường là lựa chọn tốt hơn nếu chúng tôi có lý thuyết hợp lý." Vì vậy, nếu bạn không thể hình thành một heuristic hợp lý, sau đó sử dụng tìm kiếm hai chiều. (Hình thành một heuristic tốt là không bao giờ dễ dàng;).)