Thuật toán Prim - Tìm Cây Khung Nhỏ Nhất

THUẬT TOÁN PRIM

Có bao giờ bao giờ bạn hỏi vì sao giữa các địa điểm trong một thành phố lại có nhiều đường đi đến như vậy. Vậy có cách nào vừa đảm bảo có đường đi giữa mọi điểm trong thành phố mà chi phí làm đường lại nhỏ nhất không. Tất nhiên là có rồi và thuật toán Prim sẽ giúp bạn giải quyế việc đấy một cách dễ dàng.

Thuật toán Prim - Tìm Cây Khung Nhỏ Nhất

THUẬT TOÁN

MÔ TẢ THUẬT TOÁN:

• Bước khởi tạo: Chọn một đỉnh làm gốc sau đó xét đường nối đỉnh gốc đến các đỉnh còn lại, nếu không có thì cho khoảng cách vô cùng.
• Bước 1.1: Chọn đỉnh có đường nối ngắn nhất đã tìm ở bước trước, đánh dấu là đã xét.
• Bước 1.2: Xét tiếp đường nối từ đỉnh trên đến các đỉnh còn lại chưa xét tới. Nếu phát hiện đỉnh có đường nối ngắn hơn bước trên thì cập nhật lại đường nối tại đỉnh đó.
• Lặp lại 2 bước trên đến khi đánh dấu hết các đỉnh.

ĐỒ THỊ MẪU:

MINH HỌA CÁCH GIẢI BẰNG TAY:

CODE:

KẾT QUẢ:

Minimum Spanning Tree: (6, 2) (6, 3) (6, 4) (4, 5) (1, 6)
Total Weight: 15

CÂY KHUNG NHỎ NHẤT:

LỜI KẾT

Trên đây là những kiến thức mà mình được dạy cũng như là tìm hiểu về thuật toán Prim, nếu còn gì sai sót các bạn hãy comment ở bên dưới cho mình biết nhé. Chúc các bạn một tuần làm việc và học tập hiệu quả!

Đọc thêm: