Kiểm tra xem có tồn tại đường đi giữa hai đỉnh trong biểu đồ tuần hoàn trực tiếp hay không - truy vấn

Question

Câu hỏi này có thể dễ dàng được giải quyết trong O (n + m) cho mỗi truy vấn, tuy nhiên điều này có thể trả lời các truy vấn đó với độ phức tạp cao hơn. (n²)?

Trong cây có thể dễ dàng thực hiện bằng cách làm việc với đơn đặt hàng trước và theo thứ tự. Tôi đã thử một cái gì đó tương tự trong DAG nhưng nó không có ý nghĩa gì cả.

Tôi cũng đã cố gắng thay đổi vấn đề này thành LCA trong vấn đề DAG, nhưng việc tìm LCA trong DAG không thể giải quyết đủ nhanh.

---

Để được chính xác với các ràng buộc chúng ta hãy nói:

n - số đỉnh, lên đến 10^5

m - số cạnh, lên đến 10^5

q - số lượng truy vấn, tối đa 10^5

Answer 1

Câu hỏi thú vị. Trực giác của tôi nói "không". Tôi đã không nghĩ rằng nó thông qua mặc dù.

Tuy nhiên (giả sử câu hỏi này không phải là câu hỏi lý thuyết), cho mục đích thực tế, bạn có thể sử dụng Bloom filter.

Một giải pháp khả thi cho vấn đề của bạn bằng cách sử dụng bộ lọc Bloom trước tiên sẽ tạo ra các đơn đặt hàng khác nhau của biểu đồ và mỗi đơn vị lưu trữ ánh xạ từ nút đến chỉ mục của nó theo thứ tự đó. Sau đó, để kiểm tra "reachability" từ N1 đến N2, bạn kiểm tra (foreach order) nếu chỉ số-of-N1 nhỏ hơn index-of-N2 (kiểm tra này là O (1)). Nếu điều này giữ cho tất cả các đơn đặt hàng, nó có thể truy cập với xác suất khá tốt (assuming K is big enough). (Tùy thuộc vào trường hợp sử dụng trong thế giới thực của bạn, thậm chí có thể được OK để thỉnh thoảng xem xét các kết quả sai, hoặc sau đó bạn có thể chạy kiểm tra O (N + M) đáng tin cậy). Khác, nó chắc chắn là không.

Answer 2

Tôi có cảm giác rằng có thể có giải pháp dọc theo các dòng sau, nhưng điều này không có nghĩa là giải pháp đầy đủ.

Cho S là tập con của các đỉnh. Đối với mỗi đỉnh V trong biểu đồ, hãy xem xét tập D_S (V), mà tôi xác định như sau: D_S (V) = {V} nếu V trong S, và ngược lại, D_S (V) là liên kết {V} với các bộ D_S (W) cho tất cả con cháu trực tiếp W của V. (Nghĩa là, nó là "tất cả các hậu duệ cuối cùng của V, nhưng dừng đệ quy bất cứ khi nào bạn nhấn một phần tử V".) Câu hỏi đặt ra là: chúng ta có thể tìm một tập hợp không S sao cho kích thước của S là O (f (N)) và D_S (V) có kích thước O (g (N)) cho tất cả V, và trong đó f và g là cận tuyến cận tính? (Có lẽ chúng ta có thể đạt được sqrt cho cả hai, ví dụ.)

Nếu chúng ta có thể tìm thấy điều này, thì tôi đề nghị chiến lược sau đây. Đối với tiền xử lý, tạo cho mỗi U trong S một bảng băm có chứa tất cả các đỉnh cuối cùng có thể truy cập từ U. Điều này có thể đạt được trong O (f (N) * M); đó không nhất thiết phải tốt hơn O (N^2), nhưng tốt hơn O (M * Q) ít nhất.

Bây giờ để trả lời truy vấn "có thể truy cập được từ V?", Điều này là tầm thường nếu V trong S. Nếu không, chúng tôi kiểm tra xem V = U, trong trường hợp đó nó cũng tầm thường. Cuối cùng, chúng tôi áp dụng cùng một quá trình cho tất cả con cháu của V, đệ quy, trả về "có" nếu câu trả lời là "có" qua một trong hai trường hợp trên, nhưng "không" chỉ khi chúng ta không bao giờ tìm thấy U. O (g (N)) bước.

Câu hỏi còn lại là cách chọn S. Tôi nghĩ nếu đồ thị phát sinh từ quá trình nào đó ở mức độ thấp hơn luật pháp quyền lực, người ta chỉ có thể lấy các đỉnh sqrt (N) với độ lệch cao nhất.Nhưng ví dụ nếu chúng ta có đồ thị trên N = 2 * K đỉnh (i, 0) và (i, 1), với K^2 cạnh: từ mỗi (i, 0) đến mỗi (j, 1); thì không có tập hợp con nào phù hợp S. Nhưng có thể các đồ thị không có S phù hợp có nhu cầu một mức độ đồng nhất chúng ta có thể khai thác ... Hoặc có thể không. Tôi không biết. Bất kỳ ý tưởng nào, hãy cho tôi biết!