Thuật toán Kruskal

Đăng bởi - Vào

💫💫💫
Bài toán: Cho đồ thị vô hướng có trọng số G = (V, E), với hàm trọng số w: E → R (R là tập các số thực. 
Tìm một MST (Minimal Spanning Tree: cây khung tối tiểu) của G:  T=(VT,ET).

Mã giả


Hướng dẫn giải tay



Nhận xét

Đăng nhận xét

Bài đăng phổ biến từ blog này

[DATABASE] Tìm mọi khóa của lược đồ quan hệ

Đăng bởi - Vào
Hình ảnh
  Cách thực hiện: Gọi K là tập khóa cần tìm B1. Tìm tập nguồn N và Tính N + F Nếu N + F  = Q +  thì suy ra lược đồ quan hệ chỉ có một khóa duy nhất là N và kết thúc thuật toán Ngược lại, qua bước 2 B2. Tìm tập trung gian TG Nếu TG =   thì lược đồ quan hệ có 1 khóa là tập nguồn N và kết thúc thuật toán Ngược lại, nếu TG ≠   thì tìm tất cả tập con khác rỗng X i  của tập TG Lấy từng X i  hợp với N => N ∪ X i  TH1 : Nếu (N ∪ X i ) + F  = Q +  thì (N ∪ X i ) là khóa, loại tính toán đối với các tập con khác của TG có chứa X i  ; thêm khóa vào tập K TH2 : Nếu (N ∪ X i ) + F  ≠ Q +  thì  (N ∪ X i ) không là khóa B3. Kết luận:  Khóa của lược đồ quan hệ là tập K ------------ Giải thích: N là tập thuộc tính nguồn (chứa những thuộc tính chỉ xuất hiện ở vế trái của các phụ thuộc hàm; các thuộc tính không xuất hiện ở cả vế trái và vế phải của phụ thuộc hàm) TG là tập thuộc t...
Xem chi tiết »

[DATABASE] Phủ tối thiểu của tập phụ thuộc hàm

Đăng bởi - Vào
Hình ảnh
Cách thực hiện: B1. Phân rã PTH sao cho VP chỉ còn 01 thuộc tính B2. Loại các thuộc tính dư thừa ở VT (không xét PTH mà VT có 01 thuộc tính) Bỏ thuộc tính ở VT khi và chỉ khi bao đóng của các thuộc tính còn lại chứa thuộc tính ở VP B3. Loại bỏ các PTH dư thừa ( không xét PTH mà thuộc tính ở VP chỉ xuất hiện một lần) B3.1: Tìm bao đóng của VT B3.2: Nếu bao đóng của VT chứa thuộc tính ở VP thì nó là PTH dư thừa, ngược lại nó không là PTH dư thừa ------------ Ví dụ : Cho lược đồ quan hệ Q=(A, B, C, D) và PTH F={AB → CD, B → C, C → D}  Tìm phủ tối thiểu?  B1. Phân rã PTH sao cho vế phải chỉ còn một thuộc tính F={AB → C, AB → D, B → C, C → D}  B2. Bỏ các thuộc tính dư thừa ở vế trái B → C, C → D : không xét vì vế trái chỉ có một thuộc tính Xét AB → C A + F-{AB → C}    = A, không chứa C nên B không thừa B + F-{AB  → C}   = BCD, chứa C nên A thừa Loại thuộc tín...
Xem chi tiết »

[DATABASE] Dạng chuẩn cao nhất của lược đồ quan hệ

Đăng bởi - Vào
Cách thực hiện: B1: Tìm mọi khóa của lược đồ quan hệ B2: Kiểm tra dạng chuẩn từ cao xuống thấp (BCNF - 3NF - 2NF - 1NF) BCNF (Boyce-Codd Normal Form)  Tất cả VT của phụ thuộc hàm là khóa (VT là siêu khóa) 3NF (Third Normal Form) Phân rã VP của phụ thuộc hàm sao cho VP chỉ chứa một thuộc tính Thỏa 1 trong 2 điều kiện: VT của phụ thuộc hàm là khóa hoặc VP là tập con của khóa 2NF (Second Normal Form) B1: Xác định các thuộc tính không là khóa B2: Tất cả thuộc tính không là khóa phải phụ thuộc đầy đủ vào khóa Trường hợp khác #1 : Cách để kiểm tra có đạt 2NF không trong trường hợp không biết cách xác định tính phụ thuộc đầy đủ: Với mỗi khóa K, tìm bao đóng của tất cả  tập con thực sự  Xi của K Nếu tồn tại bao đóng  X i +  chứa thuộc tính không khóa thì không đạt dạng chuẩn 2, ngược lại đạt dạng chuẩn 2 #2 : Nếu lược đồ chỉ có 01 khóa và khóa đó chỉ có duy nhất 01 thuộc tính thì chắc chắn đạt dạng chuẩn 2 1NF (First Normal Form)  Nếu lược đồ quan hệ không đạ chuẩn...
Xem chi tiết »