Tìm cây bao trùm nhỏ nhất dùng thuật toán prim

Chào các bạn,bài trước mình đã làm bài tập về tìm cây bao trùm mà dùng thuật toán Kruskal,hôm nay,mình sẽ giải lại bài toán này bằng một thuật toán mới cách thức hoặc động hoàn toàn khác.Đó là thuật toán Prim.Chúng ta cùng tìm hiểu về lý thuyết của thuật toán này nhé!

Trong khoa học máy tính, thuật toán Prim là một thuật toán tham lam để tìm cây bao trùm nhỏ nhất của một đồ thị vô hướng có trọng số liên thông. Nghĩa là nó tìm một tập hợp các cạnh của đồ thị tạo thành một cây chứa tất cả các đỉnh, sao cho tổng trọng số các cạnh của cây là nhỏ nhất.

Mô tả:

Thuật toán xuất phát từ một cây chỉ chứa đúng một đỉnh và mở rộng từng bước một, mỗi bước thêm một cạnh mới vào cây, cho tới khi bao trùm được tất cả các đỉnh của đồ thị. ==>Cái này cho ta biết tham số nhận vào và điều kiện dừng của phương thức mình sắp viết nè.
  • Dữ liệu vào: Một đồ thị có trọng số liên thông với tập hợp đỉnh V và tập hợp cạnh E (trọng số có thể âm). Đồng thời cũng dùng VE để ký hiệu số đỉnh và số cạnh của đồ thị.
  • Khởi tạo: Vmới = {x}, trong đó x là một đỉnh bất kì (đỉnh bắt đầu) trong V, Emới = {}
  • Lặp lại cho tới khi Vmới = V:
    • Chọn cạnh (u, v) có trọng số nhỏ nhất thỏa mãn u thuộc Vmớiv không thuộc Vmới (nếu có nhiều cạnh như vậy thì chọn một cạnh bất kì trong chúng)
    • Thêm v vào Vmới, và thêm cạnh (u, v) vào Emới
  • Dữ liệu ra: VmớiEmới là tập hợp đỉnh và tập hợp cạnh của một cây bao trùm nhỏ nhất

Mã giả:

Prim(G: liên thông, có trọng số, v0; đỉnh băt đầu)
begin ET := ;VT={v0};
// VT là tập đỉnh của T, ET: tập cạnh của T
while (|ET| < n-1)
begin
Tính (VT) = {(i,j)E/ i VT  j  V –VT}
Chọn cạnh e=(u,v) trong (VT) có trọng số bé nhất, bổ sung e vào T (Nghĩa là: ET=ET  {e}; VT = VT  {v})
end
return T=;
end

Trên đó là phần lý thuyết mình đã search tham khảo trên wiki,giờ mình đi thẳng vào code luôn nhé!

Dựa vào phần mã giả mình đã viết code như sau,mình có chú thích cho các bạn rồi,các bạn xem xem có hiểu không nhé,nếu có thắc đừng quên comment bạn nhé,nếu mình chậm trả lời thì liên hệ facebook mình hổ trợ trực tiếp luôn nè.

Một ví dụ nhỏ mình tham khảo trên wiki,các bạn xem để hiểu hơn về cách thức hoạt động của thuật toán nhé!

Hình minh họa U Cạnh (u,v) V \ U Mô tả
Prim Algorithm 0.svg {} {A,B,C,D,E,F,G} Đây là đồ thị có trọng số ban đầu. Các số là các trọng số của các cạnh.
Prim Algorithm 1.svg {D} (D,A) = 5 V
(D,B) = 9
(D,E) = 15
(D,F) = 6
{A,B,C,E,F,G} Chọn một cách tùy ý đỉnh D là đỉnh bắt đầu. Các đỉnh A, B, EF đều được nối trực tiếp tới D bằng cạnh của đồ thị. A là đỉnh gần D nhất nên ta chọn A là đỉnh thứ hai của cây và thêm cạnh AD vào cây.
Prim Algorithm 2.svg {A,D} (D,B) = 9
(D,E) = 15
(D,F) = 6 V
(A,B) = 7
{B,C,E,F,G} Đỉnh được chọn tiếp theo là đỉnh gần D hoặc A nhất. B có khoảng cách tới D bằng 9 và tới A bằng 7, E có khoảng cách tới cây hiện tại bằng 15, và F có khoảng cách bằng 6. F là đỉnh gần cây hiện tại nhất nên chọn đỉnh F và cạnh DF.
Prim Algorithm 3.svg {A,D,F} (D,B) = 9
(D,E) = 15
(A,B) = 7 V
(F,E) = 8
(F,G) = 11
{B,C,E,G} Thuật toán tiếp tục tương tự như bước trước. Chọn đỉnh B có khoảng cách tới A bằng 7.
Prim Algorithm 4.svg {A,B,D,F} (B,C) = 8
(B,E) = 7 V
(D,B) = 9 chu trình
(D,E) = 15
(F,E) = 8
(F,G) = 11
{C,E,G} Ở bước này ta chọn giữa C, E, và G. C có khoảng cách tới B bằng 8, E có khoảng cách tới B bằng 7, và G có khoảng cách tới F bằng 11. E là đỉnh gần nhất, nên chọn đỉnh E và cạnh BE.
Prim Algorithm 5.svg {A,B,D,E,F} (B,C) = 8
(D,B) = 9 chu trình
(D,E) = 15 chu trình
(E,C) = 5 V
(E,G) = 9
(F,E) = 8 chu trình
(F,G) = 11
{C,G} Ở bước này ta chọn giữa CG. C có khoảng cách tới E bằng 5, và G có khoảng cách tới E bằng 9. Chọn C và cạnh EC.
Prim Algorithm 6.svg {A,B,C,D,E,F} (B,C) = 8 chu trình
(D,B) = 9 chu trình
(D,E) = 15 chu trình
(E,G) = 9 V
(F,E) = 8 chu trình
(F,G) = 11
{G} Đỉnh G là đỉnh còn lại duy nhất. Nó có khoảng cách tới F bằng 11, và khoảng cách tới E bằng 9. E ở gần hơn nên chọn đỉnh G và cạnh EG.
Prim Algorithm 7.svg {A,B,C,D,E,F,G} (B,C) = 8 chu trình
(D,B) = 9 chu trình
(D,E) = 15 chu trình
(F,E) = 8 chu trình
(F,G) = 11 chu trình
{} Hiện giờ tất cả các đỉnh đã nằm trong cây và cây bao trùm nhỏ nhất được tô màu xanh lá cây. Tổng trọng số của cây là 39.

Chúc các bạn hoàn thành tốt bài tập này nhé!

Lưu ý là thuật toán trên mình tự code nên chắc chắn không thể không có sai sót nên mong các bạn thông cảm và chỉ dùng để tham khảo thôi nhé.

Giấy phép Creative Commons Giấy phép Creative Commons Attribution-ShareAlike 4.0 Quốc tế .

Tạo tài khoản



Đăng nhập


Quên mật khẩu

Hoặc là :