TÌM CÂY PHỦ TỐI TIỂU CỦA ĐỒ THỊ VÔ HƯỚNG G
BÀI TOÁN
Tìm cây phủ tối tiểu của đồ thị vô hướng G.
THUẬT TOÁN PRIM
CODE MẪU
Code:
(*BAI TOAN : LAP DIEN THOAI
THUAT TOAN : PRIM - NGUYEN LY THAM LAM*)
(*Ma tran doi xung cap n duoc phat sinh ngau nhien trong doan [a, b]*)
MaTranDoiXung[n_, a_, b_] := Module[{L, i, j},
L = Table[0, {i, n}, {j, n}];
For[i = 2, i ≤ n, i++,
For[j = 1, j < i, j++,
L[[i, j]] = L[[j, i]] = Random[Integer, {a, b}];
];
];
Return[L];
];
(*Thuat toan Prim tim cay phu toi tieu*)
ThuatToanPrim[A_, n_] := Module[{m, M, L, W, i, j, Dem, u, v, min, w},
(*Lay 1 dinh ngau nhien m lam dinh bat dau*)
m = Random[Integer, {1, n}];
(*M : luu tap dinh duoc lay*)
M = {m};
(*L : luu canh duoc di qua*)
L = {};
(*w : tong trong so nho nhat*)
w = 0;
Dem = 1;
While[Dem < n,
min = ∞;
For[i = 1, i ≤ Dem, i++,
For[j = 1, j ≤ n, j++,
If[Intersection[M, {j}] == {} && A[[M[[i]], j]] > 0 && min > A[[M[[i]], j]],
u = M[[i]];
v = j;
min = A[[u, v]];
];
];
];
w += A[[u, v]];
M = Append[M, v];
L = Append[L, {u, v}];
Dem++;
];
Return[{L, w}];
];
Clear[n, a, A, b, L];
n = Input["Nhap so dinh cua do thi G "];
a = Input["Nhap a = "];
b = Input["Nhap b = "];
A = MaTranDoiXung[n, a, b];
Print["------- Thuat toan Prime --------"];
Print["So dinh n = ", n];
Print["Ma tran doi xung duoc tao ngau nhieu trong khoang [", a, ",", b, "]"];
Print[MatrixForm[A]];
L = ThuatToanPrim[A, n];
Print["Trong so nho nhat w = ", L[[2]]];
Print["Canh duoc chon:", L[[1]]];