Thuật toán Prim (tiếng anh: Prim’s algorithm) là 1 trong những thuật toán tham lam được dùng để làm tìm cây khung bé dại nhất (Minimum Spanning Tree – MST) của một thứ thị liên thông bao gồm trọng số. Thuật toán được search ra vào khoảng thời gian 1975 và chọn cái tên theo nhà phân tích khoa học máy vi tính Robert C. Prim.

Bạn đang xem: Tìm cây khung nhỏ nhất bằng thuật toán prim

Một số thuật ngữ liên quan:

Spanning Tree : là cây khung của thiết bị thị liên thông và vô hướng, (Cho đề xuất thuật toán này chỉ thực hiện cho đồ gia dụng thị vô hướng).Minimum Spanning Tree : là cây khung nhỏ tuổi nhất, (Có tổng trọng số của những cạnh là nhỏ dại nhất).

NỘI DUNG BÀI VIẾT


Ý tưởng thuật toán Prim

Thuật toán Prim sẽ ban đầu bằng việc chọn bỗng dưng một đỉnh bất kỳ và tiếp tục thêm các cạnh gồm trọng số nhỏ dại nhất cho đến khi gồm đủ tập hợp những đỉnh. Công việc để thực hiện:

Bước 1. Khởi sản xuất tập đúng theo đỉnh V rỗng, tập đúng theo cạnh E rỗng.Bước 2. Chọn đột nhiên 1 đỉnh và phân phối tập hợp những đỉnh V.Bước 3. Lựa chọn 1 đỉnh chưa xuất hiện trong tập V mà tất cả kết nối với cùng 1 đỉnh trong V, cạnh tạo nên từ 2 đỉnh đó cần là cạnh có trọng số nhỏ nhất và tiếp tế tập hợp các cạnh E.Bước 4. Lặp lại bước 3 cho tới khi cây khung dứt (Cách nhận ra cây khung ngừng là toàn bộ các đỉnh của cây khung phần lớn đã mở ra trong V), cây khung bé dại nhất là cây size được sinh sản từ tập những cạnh trong E.

Ví dụ của thuật toán Prim

Nếu các bạn cảm thấy chưa nắm rõ thì chớ lo bọn họ sẽ lấn sân vào phần ví dụ với hình ảnh chắc chắn bạn sẽ cảm thấy dễ dàng nắm bắt hơn đấy.

Hãy quan tiếp giáp ví dụ cùng với cây khung rất đầy đủ dưới đây.

*
*
*
*
*
*
*
*
So sánh 2 cây size (ban đầu, bên trái) và cây khung nhỏ tuổi nhất tìm được bằng thuật toán Prim (bên phải).

Xem thêm: Điều Kiện Để Hai Đường Thẳng Song Song Song Khi Nào, Điều Kiện Để 2 Đường Thẳng Song Song

Code giải mã Prim

Dưới đó là hàm chính thực thi giải mã Prim màn biểu diễn đồ thi bởi ma trận kề, đi kèm với hướng dẫn bằng comment.