Có cấu trúc dữ liệu cho DAG hỗ trợ chỉnh sửa hiệu quả không?

Question

Tôi đang tìm cấu trúc dữ liệu sẽ lưu trữ bất kỳ DAG nào, nhưng hiệu quả (tức là phụ tuyến tính trong số cạnh/đỉnh) phát hiện nếu thêm cạnh sẽ tạo chu trình (và do đó ngăn bạn phá vỡ bất biến acyclic). Có ai biết điều đó không?

Cảm ơn!

Answer 1

Bạn có thể duy trì cơ sở hạ tầng về đồ thị transitive closure. Sau đó kiểm tra xem việc thêm một cạnh có gây ra các chu kỳ được thực hiện trong thời gian không đổi; nếu bạn muốn thêm cạnh (i, j), hãy kiểm tra xem đã có đường đi từ j đến i chưa. Tuy nhiên, việc cập nhật cơ sở hạ tầng có thể tốn kém hơn nói chung (xem ví dụ: La Poutré and van Leeuwen).