tailieunhanh - Introduction to Algorithms Second Edition Instructor’s Manual 2nd phần 8

Các thuật toán tham lam làm không phải lúc nào cũng mang lại một giải pháp tối ưu. Nhưng đôi khi họ làm. Chúng ta sẽ thấy một vấn đề mà họ làm. Sau đó, chúng tôi sẽ xem xét một số đặc điểm chung của các thuật toán tham lam cho giải pháp tối ưu | 21-2 Lecture Notes for Chapter 21 Data Structures for Disjoint Sets Analysis Since Make-Set counts toward total of operations m n. Can have at most n 1 Union operations since after n 1 Unions only 1 set remains. Assume that the first n operations are Make-Set helpful for analysis usually not really necessary . Application dynamic connected components. For a graph G V E vertices u v are in same connected component if and only if there s a path between them. Connected components partition vertices into equivalence classes. Connected-Components V E for each vertex v e V do Make-Set v for each edge u v e E do if Find-Set u Find-Set v then Union u v Same-Component u v if Find-Set u Find-Set v then return TRUE else return FALSE Note If actually implementing connected components each vertex needs a handle to its object in the disjoint-set data structure each object in the disjoint-set data structure needs a handle to its vertex. Linked list representation Each set is a singly linked list. Each list node has fields for the set member pointer to the representative next List has head pointer to representative and tail. Make-Set create a singleton list. Find-Set return pointer to representative. UNioN a couple of ways to do it. 1. Union x y append x s list onto end of y s list. Use y s tail pointer to find the end. Lecture Notes for Chapter 21 Data Structures for Disjoint Sets 21-3 Need to update the representative pointer for every node on x s list. If appending a large list onto a small list it can take a while. Operation objects updated UNION x1 x2 Union x2 x3 Union x3 x4 UNION x4 x5 1 2 3 4 UNlON xn_1 xn n 1 0 n2 total Amortized time per operation n . 2. Weighted-union heuristic Always append the smaller list to the larger list. A single union can still take Q n time . if both sets have n 2 members. Theorem With weighted union a sequence of m operations on n elements takes O m n lg n time. Sketch of proof Each Make-Set and Find-Set still takes O 1 . How many times can