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 nhỏ tuổi nhất (Minimum Spanning Tree – MST) của một đồ gia dụng thị liên thông bao gồm trọng số. Thuật toán được tìm kiếm ra vào năm 1975 và được lấy tên theo nhà nghiên cứu khoa học máy tính Robert C. Prim.
Bạn đang xem: Thuật toán tìm cây khung nhỏ nhất
Một số thuật ngữ liên quan:
Spanning Tree : là cây khung của vật thị liên thông cùng vô hướng, (Cho đề xuất thuật toán này chỉ thực hiện cho thiết bị thị vô hướng).Minimum Spanning Tree : là cây khung nhỏ nhất, (Có tổng trọng số của những cạnh là nhỏ nhất).NỘI DUNG BÀI VIẾT
Ý tưởng thuật toán Prim
Thuật toán Prim sẽ bước đầu bằng vấn đề chọn bỗng dưng một đỉnh bất cứ và thường xuyên thêm các cạnh tất cả trọng số nhỏ dại nhất cho đến khi gồm đủ tập hợp các đỉnh. Công việc để thực hiện:
Bước 1. Khởi chế tạo tập thích hợp đỉnh V rỗng, tập thích hợp cạnh E rỗng.Bước 2. Chọn thiên nhiên 1 đỉnh và cấp dưỡng tập hợp các đỉnh V.Bước 3. Chọn 1 đỉnh chưa tồn tại trong tập V mà gồm kết nối với 1 đỉnh vào V, cạnh tạo nên từ 2 đỉnh đó yêu cầu là cạnh gồm trọng số nhỏ dại nhất và cung cấp tập hợp những cạnh E.Bước 4. Tái diễn bước 3 cho tới khi cây khung chấm dứt (Cách nhận thấy cây khung xong xuôi là toàn bộ các đỉnh của cây khung phần đông đã lộ diện trong V), cây khung nhỏ dại nhất là cây khung được chế tạo ra từ tập các cạnh vào 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ì đừng lo bọn họ sẽ bước vào phần ví dụ và hình hình ảnh chắc chắn bạn sẽ cảm thấy dễ hiểu hơn đấy.
Hãy quan cạnh bên ví dụ cùng với cây khung không thiếu dưới đây.
Xem thêm: Máy In Hóa Đơn Bán Lẻ - Máy In Hóa Đơn Bán Hàng, Máy In Bill Giá Rẻ
Code lời giải Prim
Dưới đây là hàm chính thực thi lời giải Prim màn biểu diễn đồ thi bằng ma trận kề, kèm theo với hướng dẫn bởi comment.