Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 9

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 9 có nội dung trình bày về cây khung nhỏ nhất, định nghĩa cạnh an toàn, giải thuật tổng quát, phép cắt, định nghĩa cạnh nhẹ, giải thuật của Kruskal, và cách thực thi giải thuật của Kruskal,... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 9Caây Khung Nhoû Nhaát Caây khung nhoû nhaátª Cho – moät ñoà thò lieân thoâng, voâ höôùng G = (V, E ) – moät haøm troïng soá w:ERª Tìm moät taäp con khoâng chöùa chu trình T  E noái taát caû caùc ñænh sao cho toång caùc troïng soá w(T) = (u, v)  T w(u, v) laø nhoû nhaát. – Taäp T laøø moät caây, vaø ñöôïc goïi laø moät caây khung nhoû nhaát.ª Baøi toaùn tìm caây khung nhoû nhaát: baøi toaùn tìm T.13.11.2004 Ch. 9: Cay khung nho nhat 2 Caây khung nhoû nhaát (tieáp)ª Giaûi baøi toaùn tìm caây khung nhoû nhaát – Giaûi thuaät cuûa Kruskal – Giaûi thuaät cuûa Prim.13.11.2004 Ch. 9: Cay khung nho nhat 3 Caây khung nhoû nhaát: ví duï 8 7 b c d 4 2 9 a 11 i 4 14 e 7 6 8 10 h g f 1 2 ° Taäp caùc caïnh xaùm laø moät caây khung nhoû nhaát ° Troïng soá toång coäng cuûa caây laø 37. ° Caây laø khoâng duy nhaát: neáu thay caïnh (b, c) baèng caïnh (a, h) seõ ñöôïc moät caây khung khaùc cuõng coù troïng soá laø 37.13.11.2004 Ch. 9: Cay khung nho nhat 4 Caïnh an toaønª Cho moät ñoà thò lieân thoâng, voâ höôùng G = (V, E ) vaø moät haøm troïng soá w : E  R. Tìm moät caây khung nhoû nhaát cho G!ª Giaûi baøi toaùn baèng moät chieán löôïc greedy: nuoâi moät caây khung lôùn daàn baèng caùch theâm vaøo caây töøng caïnh moät.ª Ñònh nghóa caïnh an toaøn Neáu A laø moät taäp con cuûa moät caây khung nhoû nhaát naøo ñoù, neáu (u, v) laø moät caïnh cuûa G sao cho taäp A  {(u, v)} vaãn coøn laø moät taäp con cuûa moät caây khung nhoû nhaát naøo ñoù, thì (u, v) laø moät caïnh an toaøn cho A.13.11.2004 Ch. 9: Cay khung nho nhat 5 Moät giaûi thuaät toång quaùt (generic)ª Moät giaûi thuaät toång quaùt (generic) ñeå tìm moät caây khung nhoû nhaát – Input: moät ñoà thò lieân thoâng, voâ höôùng G moät haøm troïng soá w treân caùc caïnh cuûa G – Output: Moät caây khung nhoû nhaát cho G. GENERIC-MST(G, w) 1 A 2 while A khoâng laø moät caây khung nhoû nhaát 3 do tìm caïnh (u, v) an toaøn cho A 4 A  A  {(u, v)} 5 return A13.11.2004 Ch. 9: Cay khung nho nhat 6 Pheùp caét Caùc khaùi nieäm quan troïngª Moät pheùp caét (S, V  S) cuûa G = (V, E ) laø moät phaân chia (partition) cuûa V. Ví duï: S = {a, b, d, e} trong ñoà thò sau.ª Moät caïnh (u, v)  E xuyeân qua (cross) moät pheùp caét (S, V  S) neáu moät ñænh cuûa noù naèm trong S vaø ñænh kia naèm trong V  S. Ví duï: caïnh (b, c). 8 7 b c d 4 2 9 a 11 i 4 14 e S 7 6 10 8 VS h g f 1 213.11.2004 Ch. 9: Cay khung nho nhat 7 Caïnh nheï (light edge) Caùc khaùi nieäm quan troïng (tieáp)ª Moät pheùp caét baûo toaøn taäp caùc caïnh A (respects A) neáu khoâng coù caïnh naøo cuûa A xuyeân qua pheùp caét.ª Moät caïnh laø moät caïnh nheï vöôït qua pheùp caét neáu troïng soá cuûa noù laø nhoû nhaát trong moïi troïng soá cuûa caùc caïnh xuyeân qua pheùp caét. Ví duï: caïnh (c, d). 8 7 b c d 4 2 9 a 11 i 4 e S 7 6 14 8 ...