Tìm Cây Khung Nhỏ Nhất Bằng Thuật Toán Prim : Tìm Cây Khung Nhỏ Nhất

Hôm nay bản thân xin share một số chú giải về Thuật toán Prim dùng làm giải bài toán tìm cây khung nhỏ tuổi nhất (Minimum Spanning Tree) mang đến đồ thị vô hướng tất cả trọng số. Prim cũng là trong số những thuật toán truyền thống để giải bài toán này.

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

Mục lục 3. Kết luận 1. Ý tưởng

Cây khung (spanning tree) của một thứ thị là 1 trong đồ thị bé liên thông không có chu trình đi qua toàn bộ các đỉnh. Một thiết bị thị sẽ có không ít cây khung và việc của bọn họ là bắt buộc tìm ra cây khung nhỏ dại nhất.

Ý tưởng cơ bản của thuật toán Prim như sau:

Bước 1: chọn 1 đỉnh v ngẫu nhiên làm đỉnh bắt đầu và chuyển đỉnh v vào cây khung.Bước 2: Thêm toàn bộ các cạnh nối cùng với v vào list cạnh sẽ xét .Bước 3: Xét những cạnh trong danh sách đến lúc hết:Bước 3.1: kéo ra cạnh bao gồm trọng số bé dại nhất nối từ v1 mang lại một đỉnh v2 chưa phía trong cây khung. Đưa cạnh này với đỉnh v2 vào cây khung.Bước 3.2: Đưa các cạnh nối từ đỉnh v2 đến các đỉnh chưa phía trong cây khung vào list cạnh đang xét.2. Ví dụ

Để phân tích và lý giải rõ hơn các bước thực hiện tại của thuật toán, bản thân xin chạy thuật toán với đồ vật thị $G$ mặt dưới:

Đồ thị $G$

Chọn đỉnh $0$ có tác dụng đỉnh bắt đầu, gửi đỉnh này vào cây khung (màu xanh). Đưa những cạnh 0-1, 0-2, 0-3 vào list cạnh sẽ xét (màu cam). Ta thấy cạnh 0-2 là cạnh có trọng số nhỏ nhất.

Đưa cạnh 0-2 và đỉnh $2$ vào cây khung. Đưa các cạnh 2-4 và 2-5 vào list đang xét. Bây giờ ta thấy cạnh 2-4 tất cả trọng số nhỏ nhất.

Đưa cạnh 2-4 và đỉnh $4$ vào cây khung. Đưa các cạnh 4-1 với 4-6 vào list đang xét. Lúc này ta thấy cạnh 4-1 có trọng số nhỏ nhất.

Đưa cạnh 4-1 với đỉnh $1$ vào cây khung. Các đỉnh nối từ $1$ là $0$ cùng $4$ đông đảo đã phía bên trong cây size nên bọn họ sẽ không đưa những cạnh nối những đỉnh này vào danh sách đang xét. Lúc này, ta xét những cạnh còn sót lại và thấy cạnh 2-5 bao gồm trọng số nhỏ dại nhất.

Đưa cạnh 2-5 và đỉnh $5$ vào cây khung. Liên tiếp đưa bố cạnh 5-3, 5-6 cùng 5-7 vào list đang xét. Cạnh 5-6 lúc này có trọng số nhỏ tuổi nhất.

Đưa cạnh 5-6 và đỉnh $6$ vào cây khung. Liên tục đưa cạnh 6-7 cùng 6-8 vào list đang xét, không chuyển cạnh 6-4 do đỉnh $4$ đã bên trong cây khung. Cạnh 6-8 hôm nay có trọng số bé dại nhất.

Đưa cạnh 6-8 và đỉnh $8$ vào cây khung. Đưa cạnh 8-7 vào danh sách đang xét. Lúc này danh sách có cạnh 6-7 tất cả trọng số nhỏ tuổi nhất.

Đưa cạnh 6-7 và đỉnh $7$ vào cây khung. Không tồn tại cạnh nào được gửi tiếp vào list đang xét vì những đỉnh kề của $7$ hầu như đã phía bên trong cây khung. Hôm nay cạnh 5-7 và 8-7 đều có trọng số nhỏ dại nhất. Tuy nhiên, cả 3 đỉnh $5$, $7$, $8$ đều đã nằm trong cây khung đề nghị sẽ bị loại bỏ. Vậy cạnh 0-3 là cạnh bao gồm trọng số nhỏ tuổi nhất.

3. Kết luận

Trên đây tôi đã trình bày rõ ràng thuật toán Prim và quá trình thực hiện trải qua ví dụ. Vì bài viết đã hơi dài yêu cầu mình sẽ trình diễn cách thiết lập thuật toán này trong bài viết sau.

References

Cảm ơn bạn

Your phản hồi has been submitted và will be published once it has been approved. 😊

Thuật toán Prim (tiếng anh: Prim’s algorithm) là một 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 đồ vật thị liên thông tất cả trọng số. Thuật toán được tìm kiếm ra vào khoảng thời gian 1975 và chọn cái tên theo nhà nghiên cứu và phân tích khoa học laptop Robert C. Prim.

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

Spanning Tree : là cây form của vật dụng thị liên thông với vô hướng, (Cho bắt buộc thuật toán này chỉ sử dụng cho đồ dùng thị vô hướng).Minimum Spanning Tree : là cây khung bé dại nhất, (Có tổng trọng số của các 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ắt đầu bằng vấn đề chọn bỗng dưng một đỉnh bất kì và liên tục thêm những cạnh tất cả trọng số bé dại nhất cho tới khi tất cả đủ tập hợp các đỉnh. Các bước để thực hiện:

Bước 1. Khởi tạo thành tập hòa hợp đỉnh V rỗng, tập hòa hợp cạnh E rỗng.Bước 2. Chọn tình cờ 1 đỉnh và cung cấp tập hợp những đỉnh V.Bước 3. Lựa chọn một đỉnh chưa tồn tại trong tập V mà bao gồm kết nối với cùng 1 đỉnh trong V, cạnh chế tác từ 2 đỉnh đó đề xuất là cạnh gồm trọng số nhỏ nhất và chế tạo 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 mọi đã mở ra trong V), cây khung bé dại nhất là cây khung được chế tác từ tập những cạnh vào E.