tailieunhanh - Thuật toán Prim – Tìm cây khung có trọng số nhỏ nhất

Thuật toán Prim 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. | Thuật toán Prim - Tìm cây khung có trọng số nhỏ nhất cây bao trùm nhũ nhất của đồ thị mặt phang. 3 Thuật toán Prim 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 ý x0 thuộc X và khởi tạo V x0 T 0. Trong đó X là tập các đỉnh của đồ thị V 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 nối đỉnh x với đỉnh y mà x E V và y E X V ta chọn cạnh e có trọng số nhỏ nhất. Nếu không có cạnh e thỏa yêu câu DỪNG 1 Bước 3 Thêm đỉnh y vào tập V và thêm cạnh e vào tập T. Bước 4 Nếu T đủ n - 1 phần tử thì DỪNG 2 ngược lại làm tiếp tục bước 2. Ghi chú Khi thuật toán dừng theo trường hợp 1 tìm không có cạnh từ V đi ra thì đồ thị không liên thông nên không có cây khung và do đó cũng không có cây khung nhỏ nhất. Cài đặt thuật toán Prim Trong các thuật toán tìm cây khung ngắn nhất chúng ta có thể bỏ đi hướng các cạnh và các khuyên đối với các cạnh song song thì có thể bỏ đi và chỉ để lại một cạnh trọng số nhỏ nhất trong chúng. Vì vậy dữ liệu nhập cho thuật toán thường là ma trận trọng số L được quy ước như sau Lij Trọng lượng cạnh nhỏ nhất nối i đến j nếu có Lij 0 nếu không có cạnh nối i đến j Ma trận có thể tổ chức bằng mảng 2 chiều tĩnh hoặc động trong bộ nhớ. Tập V có thể tổ chức bằng một mảng 1 chiều tĩnh hoặc động lưu các đỉnh hoặc là một mảng dùng để dánh dấu theo kiểu hàm đặc trưng V i 1 nếu i thuộc V và V i 0 nếu ngược lại . Bài tập Sử dụng thuật toán Prim để tìm cây khung nhỏ nhất trong đồ thị vô hướng có trọng số. Cấu trúc file dữ liệu đầu vào Dòng đầu tiên số đỉnh đồ thị N N dòng tiếp theo ma trận kề của đồ thị với quy ước A i j W trọng số của đường nối trực tiếp từ i đến j A i j 0 không có đường nối trực tiếp từ i đến j Các đỉnh được đánh chỉ số từ 0 Cấu trúc file dữ liệu đầu ra Nếu tìm được cây khung nhỏ nhất Dòng đầu chứa số nguyên k là trọng lượng cây khung cực tiểu Dòng tiếp theo là các cạnh u v thuộc cây khung này Nếu .