Thuật toán Prim – Tìm cây bao trùm nhỏ nhất

1. Mô tả:

Giống như Kruskal, Prim cũng tìm cây khung nhỏ nhất, tuy nhiên Prim phụ thuộc vào đỉnh xuất phát của quá trình tìm kiếm.

– Hình 1: Đây là đồ thị có trọng số ban đầu. Các số là các trọng số của các cạnh.

Hình 1

– Hình 2: 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.

Hình 2

– Hình 3: Đỉ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 Abằ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.

Hình 3

– Hình 4: 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.

Hình 4

– Hình 5: Ở 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.

Hình 5

– Hình 6: Ở 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 Ebằng 9. Chọn C và cạnh EC.

Hình 6

– Hình 7: Quá trình tìm đỉnh kế tiếp không được tạo ra một chu trình so với ban đầu, để biết được đỉnh mới được chọn có trở thành chu trình hay không, ta cần kiểm tra đỉnh đó đã được đi qua hay chưa, nếu đã đi qua thì không thể đi tới, trong trường hợp này là đỉnh B và đỉnh F đều có trọng số mới là 8 (nhỏ nhất) nhưng ta không chọn. Như vậy, đỉ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.