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]]];