Đang chuẩn bị liên kết để tải về tài liệu:
Cấu trúc dữ liệu và giải thuật - Chương 18

Tài liệu tham khảo dành cho giáo viên, sinh viên chuyên ngành công nghệ thông tin - Giáo trình cấu trúc dữ liệu và giải thuật do các giáo viên trường đại học hoa sen biên soạn. | UNIVERSITY Minimum spanning tree Khái niệm x 1 J K J 1 Ả IK n r rri - Cây bao trùm tôi thiêu MST minimum spanning tree của một đô thị có trọng sô là một tập hợp các 1 1 Ấ. Ấ .A. 7 X J.7 1 1 . Ấ 7 cạnh kêt nôi tât cả các đỉnh sao cho tông trọng sô của X 1 1 X 17 1 Ấ các cạnh là nhỏ nhât IK 1 1 V 1 Ấ 1 Ấ 1 X 1 1 Ấ V J 4- J1 - MST không nhât thiêt là duy nhât trong một đô thị UNIVERSITY Minimum spanning tree Ví dụ HOA SEN UNIVERSITY Thuật toán Dijkstra-Prim Giới thiệu - Thuật toán do Edsger Dijkstra và R.C. Prim tìm ra vào năm 1950 một cách độc lập - Giải thuật Prim dùng để giải bài toán cây bao trùm tối thiểu. - Giải thuật này sử dụng chiến lược để giải một bài toán tối ưu hóa giải thuật tham lam greedy Tại mỗi bước của giải thuật ta phải chọn một trong một số khả năng lựa chọn. Chiến lược tham lam đề xuất việc lựa chọn khả năng tốt nhất tại lúc .