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.

1

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, EF đều được nối trực tiếp tới 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.

 2

Hình 2

  Hình 3: Đỉnh được chọn tiếp theo là đỉnh gần D hoặc 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.

3

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.

4

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. là đỉnh gần nhất, nên chọn đỉnh E và cạnh BE.

5

Hình 5

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

6

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.

7

Hình 7

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

8

Hình 8

Nguồn từ: http://vi.wikipedia.org/wiki/Thu%E1%BA%ADt_to%C3%A1n_Prim

2. Cài đặt:

Bước 1: Khởi tạo các biến:

Untitled

Bước 2: Cài đặt các bước thực hiện trong thuật toán Prim:
UntitledHàm tìm nút kế tiếp:

Untitled

Như vậy là tôi vừa hướng dẫn các bạn cách cài đặt thuật toán Prim – tìm cây bao trùm nhỏ nhất, chúc các bạn thành công ^_^

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

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất /  Thay đổi )

Google photo

Bạn đang bình luận bằng tài khoản Google Đăng xuất /  Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất /  Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất /  Thay đổi )

Connecting to %s