ĐỀ TÀI: CÂy bao trùm nhỏ nhất học viên thực hiệN
tải về 0.76 Mb.
|
ATHTTT DDOS
| kktspaningtree (G(V,E),w(.)):
1. if V=1 2. return G 3. X← BorůvkaStep (G,w(.)) 4. Y← BorůvkaStep (G,w(.)) 5. H← Sampling edges of G with p=1/2 6. F← kktspanningtree(H,w(.)) 7. Z← the set of F-heavy edges in G. 8. G0←G∖Z ≪ remove Z from G≫ 9. T← kktspanningtree (G0,w(.)) 10. return BoruvkaStep(G(V,E),w(.)) -> O(V) 1. X← the set of safe edges 2. G←G/X ≪ contract the set of edges X≫ 3. return *Độ phức tạp bài toán: Đối với một đồ thị đã cho G = (V; E) với |V | = n và |E| = m, chúng ta biểu diễn thời gian chạy là T (m; n). Phân tích có thể được chia nhỏ hơn như sau: 1. Hai bước của Boruvka chạy trong O (m) 2. Đệ quy trên H chạy trong T (m1; n1) 3. Nhận dạng các cạnh nặng F chạy trong O (m1) 4. Cuộc gọi đệ quy trên G0 chạy trong T (m2; n2) 5. Kết nối các cạnh từ các bước trước đó chạy bằng O (m) Số cạnh trong đồ thị con, m1 và m 2 bị giới hạn bởi m, do đó thời gian chạy tổng thể là O (m) chỉ phụ thuộc vào số cạnh trong đồ thị G. Trong trường hợp xấu nhất, khi bước ngẫu nhiên hóa không giúp tăng tốc quá trình, thuật toán ngẫu nhiên này chỉ đơn giản trở thành thuật toán Boruvka và chạy trong thời gian O (m log n). 1 Nguồn ảnh: https://edward-huang.com 2 Nguồn ảnh: https://www.cisco.com tải về 0.76 Mb. Chia sẻ với bạn bè của bạn:
|