THUẬT TOÁN PRIM VÀ KRUSKAL

Tiếp tục với chủ đề đồ thị, hai thuật toán Prim và kruskal đều tìm cây khung cực tiểu nhỏ nhất. Hai thuật toán trên được viết bằng ngôn ngữ Pascal, với kết quả ra file "prim.out" hay "kruskal.out", file dữ liệu ma trận kề là "prim.inp" hay "kruskal.inp"

Đề bài thuật toán:

Bài: Cho đồ thị vô hướng, có trọng số G gồm n đỉnh, m cạnh. Hãy tìm cây khung cực tiểu của đồ thị G theo thuật toán Prim?
Dữ liệu vào file 'Prim.inp': Dòng đầu là 2 số n, m; m dòng tiếp theo là m bộ 3 số i, j, k mỗi số cách nhau một dấu cách, thể hiện 2 đỉnh i, j có cạnh nối với nhau có độ dài là k.
Kết quả ghi ra file 'Prim.out': Dòng đầu là tổng độ dài của cây khung cực tiểu; các dòng tiếp theo là danh sách các cạnh được chọn trong cây khung.

Bài: Cho đồ thị vô hướng, có trọng số G gồm n đỉnh, m cạnh. Hãy tìm cây khung cực tiểu của đồ thị G theo thuật toán Kruskal?
Dữ liệu vào file 'Kruskal.inp' dòng đầu là 2 số n, m; m dòng tiếp theo là m bộ 3 số i, j, k mỗi số cách nhau một dấu cách, thể hiện 2 đỉnh i, j có cạnh nối với nhau có độ dài là k.
Kết quả ghi ra file 'Kruskal.out' dòng đầu là tổng độ dài của cây khung cực tiểu; các dòng tiếp theo là danh sách các cạnh được chọn trong cây khung.

Thuật toán Kruskal
Thuật toán Prim