Thuật toán prim tìm cây khung nhỏ nhất c++ năm 2024

Môn: Lí thuyết đồ thị Lớp 10HCA2/10HCB

GVHDTH: 1

Phạm Trọng Nghĩa, Nguyễn Hoàng Khai, Bùi Thị Danh, Phạm Hoài Vũ

Tìm cây khung nhỏ nhất

Thuật toán Prim

9. Thuật toán

Cho G=(X,E) là một đồ thị liên thông có trọng số gồm n đỉnh. Thuật toán

Prim được dùng để tìm ra cây khung nhỏ nhất của G.

Bước 1: Chọn tùy ý v  X và khởi tạo Y:= {v}; T := Ø. Trong đó X là tập

các đỉnh của đồ thị, Y là tập các đỉnh được chọn vào cây khung nhỏ nhất và T là

tập các cạnh của cây này.

Bước 2: Trong số những cạnh e nối đỉnh w với đỉnh v trong Y với w  X\Y

và v  Y ta chọn cạnh có trọng lượng nhỏ nhất.

Bước 3: Gán Y := Y  {w} và T:= T  {e}

Bước 4: Nếu T đủ n – 1 phần tử thì dừng, ngược lại làm tiếp tục bước 2.

Chú ý: trong các thuật toán tìm khung nhỏ nhất chúng ta có thể bỏ đi hướng các

cạnh và các khuyên; đối với cạnh song song thì có thể bỏ đi và chỉ để lại một cạnh

trọng lượng nhỏ nhất trong chúng.

II. Ví dụ

Tìm cây khung nhỏ nhất của đồ thị sau: