TAILIEUCHUNG - 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! | Cây Khung Nhỏ Nhất Cây khung nhỏ nhất ª Cho một đồ thị liên thông vô hướng G V E một hàm trọng số w E R ª Tìm một tập con không chứa chu trình T E nối tất cả các đỉnh sao cho tổng các trọng số w T u v T w u v là nhỏ nhất. Tập T làø một cây và được gọi là một cây khung nhỏ nhất. ª Bài toán tìm cây khung nhỏ nhất bài toán tìm T. Ch. 9 Cay khung nho nhat 2 Cây khung nhỏ nhất tiếp ª Giải bài toán tìm cây khung nhỏ nhất Giải thuật của Kruskal Giải thuật của Prim. Ch. 9 Cay khung nho nhat 3 Cây khung nhỏ nhất ví dụ 8 7 b c d 4 2 9 a 11 i 4 14 e 7 6 8 10 h g f 1 2 Tập các cạnh xám là một cây khung nhỏ nhất Trọng số tổng cộng của cây là 37. Cây là không duy nhất nếu thay cạnh b c bằng cạnh a h sẽ được một cây khung khác cũng có trọng số là 37. Ch. 9 Cay khung nho nhat 4 Cạnh an toàn ª Cho một đồ thị liên thông vô hướng G V E và một hàm trọng số w E R. Tìm một cây khung nhỏ nhất cho G ª Giải bài toán bằng một chiến lược greedy nuôi một cây khung lớn dần bằng cách thêm vào cây từng cạnh một. ª Định nghĩa cạnh an toàn Nếu A là một tập con của một cây khung nhỏ nhất nào đó nếu u v là một cạnh của G sao cho tập A u v vẫn còn là một tập con của một cây khung nhỏ nhất nào đó thì u v là một cạnh an toàn cho A. Ch. 9 Cay khung nho nhat 5 Một giải thuật tổng quát generic ª Một giải thuật tổng quát generic để tìm một cây khung nhỏ nhất Input một đồ thị liên thông vô hướng G một hàm trọng số w trên các cạnh của G Output Một cây khung nhỏ nhất cho G. GENERIC-MST G w 1 A 2 while A không là một cây khung nhỏ nhất 3 do tìm cạnh u v an toàn cho A 4 A A u v 5 return A Ch. 9 Cay khung nho nhat 6 Phép cắt Các khái niệm quan trọng ª Một phép cắt S V S của G V E là một phân chia partition của V. Ví dụ S a b d e

• Cơ sở dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu và giải thuật
• Cây khung nhỏ nhất
• Đồ thị liên thông
• Giải thuật Kruskal
• Giải thuật Prim
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• tài liệu Cấu trúc dữ liệu và giải thuật
• giáo trình Cấu trúc dữ liệu và giải thuật
• bài tập Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu
• Ngôn ngữ diễn đạt giải thuật
• Thiết kế và phân tích giải thuật
• Giải thuật đệ quy
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu cơ bản
• Kiểu dữ liệu trừu tượng
• Tổng quan về giải thuật
• Kiểu dữ liệu
• Các tiêu chuẩn đánh giá dữ liệu
• Cách diễn đạt giải thuật
• Phân tích giải thuật
• phân tích thiết kế
• thiết kế hướng đối tượng
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm