Buzz
| Thuật toán tìm kiếm cây và đồ thị |
|---|
|
| Danh sách |
|
| Liên quan |
|
Trong lĩnh vực khoa học máy tính, thuật toán Prim là một thuật toán tham lam nhằm tìm cây khung nhỏ nhất của đồ thị vô hướng có trọng số liên thông. Nó tìm tập hợp các cạnh tạo thành một cây chứa tất cả các đỉnh sao cho tổng trọng số là nhỏ nhất. Thuật toán này được phát hiện năm 1930 bởi Vojtěch Jarník, sau đó Robert C. Prim năm 1957 và Edsger Dijkstra năm 1959 cũng độc lập phát hiện lại. Vì thế nó còn được biết đến như thuật toán DJP, thuật toán Jarník, hay thuật toán Prim–Jarník.
Một số thuật toán đơn giản khác cho bài toán này gồm có thuật toán Kruskal và thuật toán Borůvka.
Mô tả
Thuật toán bắt đầu với một cây chứa đúng một đỉnh và mở rộng từng bước bằng cách thêm một cạnh mới vào cây, cho đến khi bao phủ toàn bộ các đỉnh của đồ thị.
- Dữ liệu vào: Một đồ thị liên thông có trọng số với tập đỉnh V và tập cạnh E (có thể có trọng số âm). Đồng thời, V và E cũng ký hiệu số đỉnh và số cạnh của đồ thị.
- Khởi tạo: Vmới = {x}, với x là một đỉnh bất kỳ (đỉnh bắt đầu) trong V, Emới = {}
- Lặp lại đến 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ới và v không thuộc Vmới (nếu có nhiều cạnh như vậy thì chọn ngẫu nhiên một cạnh)
- Thêm v vào Vmới, và thêm cạnh (u, v) vào Emới
- Dữ liệu ra: Vmới và Emới là tập đỉnh và tập cạnh của cây khung nhỏ nhất
Độ phức tạp tính toán
| Cấu trúc dữ liệu tìm cạnh có trọng số nhỏ nhất | Độ phức tạp thời gian (tổng cộng) |
|---|---|
| Tìm kiếm trên ma trận kề | O(V) |
| Đống nhị phân và danh sách kề | O((V + E) log V) = O(E log V) |
| Đống Fibonacci và danh sách kề | O(E + V log V) |
Một cách lập trình đơn giản sử dụng ma trận kề và tìm kiếm toàn bộ mảng để tìm cạnh nhỏ nhất có thời gian chạy O(V). Sử dụng đống nhị phân và danh sách kề, thời gian chạy giảm xuống O(E log V). Sử dụng đống Fibonacci phức tạp hơn, thời gian chạy giảm xuống O(E + V log V), nhanh hơn khi đồ thị có số cạnh E=ω(V).
Ví dụ
| Hình minh họa | U | Cạnh (u,v) | V \ U | Mô tả |
|---|---|---|---|---|
| {} | {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. | ||
| {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, E và F đề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. | |
| {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. | |
| {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. | |
| {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. | |
| {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 C và G. 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. | |
| {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. | |
| {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ứng minh
Đặt G là một đồ thị liên thông có trọng số. Tại mỗi bước, thuật toán Prim chọn một cạnh nối từ đồ thị con đến một đỉnh chưa thuộc đồ thị con. Vì G liên thông nên luôn tồn tại đường từ mỗi đồ thị con tới các đỉnh khác. Kết quả T của thuật toán Prim là một cây, vì các cạnh và đỉnh thêm vào T là liên thông và cạnh mới thêm không bao giờ tạo thành chu trình. Đặt T1 là cây bao trùm nhỏ nhất của G. Nếu T1=T thì T là cây bao trùm nhỏ nhất. Nếu không, đặt e là cạnh đầu tiên thêm vào T không thuộc T1, và V là tập đỉnh của T trước khi thêm e. Một đầu của e thuộc V, đầu kia không. Vì T1 là cây bao trùm của G, tồn tại đường trong T1 nối hai đầu của e. Trên đường đó có cạnh f nối một đỉnh trong V với một đỉnh ngoài V. Khi e được thêm vào Y, thuật toán có thể chọn f nếu trọng số nhỏ hơn e. Vì f không được chọn nên
Đặt T2 là đồ thị khi xóa f và thêm e vào T1. Dễ thấy T2 liên thông, có số cạnh như T1 và tổng trọng số không lớn hơn T1, nên nó là cây bao trùm nhỏ nhất của G và chứa e cùng các cạnh được chọn trước đó. Lặp lại lập luận này, cuối cùng ta có cây bao trùm nhỏ nhất của G giống T. Vì vậy T là cây bao trùm nhỏ nhất.
- V. Jarník (1930), “O jistém problému minimálním”, Práce Moravské Přírodovědecké Společnosti, 6: 57–63 (Tiếng Séc)
- R. C. Prim (1957), “Shortest connection networks and some generalizations”, Bell System Technical Journal, 36: 1389–1401(Tiếng Anh)
- Cheriton, David; Tarjan, Robert E. (1976), “Finding minimum spanning trees”, SIAM Journal on Computing, 5 (4): 724–741(Tiếng Anh)
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009), Introduction to Algorithms (ấn bản 3), MIT Press, ISBN 0-262-03384-4 Phần 23.2: The algorithms of Kruskal and Prim, tr. 631–638.(Tiếng Anh)
Liên kết ngoài
- Applet mô phỏng thuật toán Prim
- Một applet khác mô tả thuật toán Prim Lưu trữ vào ngày 12-07-2006 tại Wayback Machine
- Chương trình Python minh họa thuật toán tìm cây khung nhỏ nhất, viết bởi Ronald L. Rivest Lưu trữ vào ngày 09-08-2011 tại Wayback Machine
