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
- 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: