Biểu đồ (cạnh trọng số dương) với MST Nếu một số cạnh, e được sửa đổi thành giá trị mới, cách tốt nhất để cập nhật MST là gì mà không hoàn toàn làm lại. Tôi nghĩ rằng điều này có thể được thực hiện trong thời gian tuyến tính. Ngoài ra, có vẻ như tôi sẽ cần một thuật toán khác nhau dựa trên việc 1) e đã là một phần của MST và 2) cho dù cạnh mới, e lớn hơn hay nhỏ hơn sốCập nhật cây bao trùm tối thiểu với sửa đổi cạnh
Giải pháp O (n) của tôi được dựa trên giả định, rằng trước khi bạn bắt đầu sửa đổi các cạnh, bạn nên tìm MST (không được đưa ra với đồ thị). Để làm như vậy, bạn có thể sử dụng thuật toán Kruskal hoạt động trong O (n log n), và như là một tác dụng phụ tạo ra danh sách sắp xếp các cạnh. Chi phí của nó bị chi phối bởi phân loại, vì vậy khi bạn sửa đổi trọng lượng của một cạnh, bạn có thể xóa nó khỏi danh sách được sắp xếp trong O (log n) và chèn nó trở lại với giá trị mới, cũng trong O (log n) và cuối cùng gọi Kruskal thuật toán một lần nữa, mà bây giờ chạy trong thời gian tuyến tính bởi vì các cạnh được sắp xếp.
Đây là giải pháp tuyến tính theo yêu cầu của bạn, nhưng có vẻ như nó có thể được thực hiện nhanh hơn.
Có 4 trường hợp:
Edge là trong MST và bạn giảm giá trị của cạnh:
Current MST vẫn là MST
cạnh không có trong MST và bạn giảm giá trị cạnh:
Thêm cạnh này vào MST. Bây giờ bạn đã có chính xác 1 chu kỳ.
Dựa trên cycle property trong MST, bạn cần phải tìm và loại bỏ cạnh có giá trị cao nhất trên chu kỳ đó. Bạn có thể làm điều đó bằng cách sử dụng dfs hoặc bfs. Độ phức tạp O (n).
Edge là trong MST và bạn tăng giá trị của nó cạnh:
Remove cạnh này từ MST. Bây giờ bạn có 2 thành phần được kết nối cần được kết nối. Bạn có thể tính cả hai thành phần trong O (n) (bfs hoặc dfs). Bạn cần phải tìm cạnh có giá trị nhỏ nhất kết nối các thành phần này. Lặp lại các cạnh theo thứ tự tăng dần theo giá trị của chúng. Độ phức tạp O (n).
cạnh không có trong MST và bạn tăng giá trị của nó cạnh:
Current MST vẫn là MST
TRƯỜNG HỢP 3. KHÔNG PHẢI (O). để lặp qua các cạnh theo thứ tự tăng dần. chúng ta cần sắp xếp chúng. có các cạnh O (n^2). ngay cả khi chúng tôi đang sử dụng các cạnh được sắp xếp mà chúng tôi đã tính toán trong khi thực hiện mst, nó vẫn sẽ phải trải qua các cạnh này (tất cả có thể trong trường hợp xấu nhất). –
Nó có thể là O (n). 1. Hủy bỏ cạnh có trọng lượng tăng lên và theo dõi hai nút được kết nối bởi cạnh này 2. Chạy bfs/dfs bắt đầu bằng hai nút này hiện có trong 2 tập hợp rời nhau. Bạn bằng cách nào đó băm các đỉnh truy cập để bạn có thể truy cập chúng trong O (1). Tôi sẽ tạo hai hashtables, một cho mỗi bộ phân chia. 3. Lặp qua tất cả các cạnh trong E-E 'trong đó G = (V, E) và MST = (V, E'). Nếu bất kỳ cạnh nào chứa 1 nút từ mỗi nút có thể bắt đầu, nó sẽ kết nối hai bộ phân tách. Duy trì một biến min để xác định cạnh nào được kết nối với hai bộ và có trọng số thấp nhất. O (E) – Olshansk
Olshansk, O (E) là O (n^2), như Ashish đã chỉ ra.Theo như tôi có thể nói, loại bỏ yêu cầu O (n^2), bởi vì đối với mỗi cạnh (giả sử được sắp xếp đã có trong danh sách), chúng ta cần tìm cạnh nhỏ nhất kết nối hai cây bao trùm. Điều này có thể chiếm đến O (n^2) nếu cạnh duy nhất kết nối chúng cũng là cạnh có giá trị cao nhất. –
Thật không may trong thuật toán Kruskal bạn cần Liên minh-tìm mà không phải là O (1) ;/ –