[C]uong
Admin
Tổng số bài gửi : 258
Điểm : 466
Ngày tham gia : 08/07/2009
Age : 31
Đến từ : Äô Thà nh CiTy
Character sheet Point: (50/50)
|
Tiêu đề: Thuật kruskal 28/07/09, 06:19 pm |
|
|
Cho đồ thị G có N đỉnh biểu diễn bằng ma trận trọng lượng (N dòng, N cột). Các biến được sử dụng: - L: ma trận trọng lượng. - n: số đỉnh của đồ thị. - CANH: biến có cấu trúc gồm 2 trường DINH1 và DINH2. - T: mảng 1 chiều của các CANH. - nT: số phần tử của mảng T (số cạnh của đồ thị). - M: mảng đánh dấu thành phần liên thông. Bước 1 Sắp xếp các cạnh của đồ thị theo thứ tự tăng dần Đặt T = ø Bước 2 Lấy 1 cạnh e (lần lượt lấy theo thứ tự đã sắp) Nếu T = T + {e} không chứa chu trình thì gán T = T + {e} Bước 3 Nếu nT = n-1 thì ngừng Ngược lại quay về Bước 2
Tìm chu trình Bước 1 Lấy ra 1 cạnh e=(u, v) thuộc T, tìm nhãn của u và v. Bước 2 Nếu nhãn của u trùng với nhãn của v, tiếp Bước 1. Ngược lại thực hiện Bước 3. Bước 3 Gộp nhãn của u và v theo qui ước lấy đỉnh có vị trí min làm đại diện. QuangHan Sep 28 2007, 02:57 AM
Code
Procedure Kruskal (G) T = V; Q =Sort(E) /* Tạo n cây, mỗi cây gồm một đỉnh*/ For each u of X do Parent(u):=-1; m = |E| For j:=1 to m do { u:=NodeStart(Q(j)); V:=NodeEnd(Q(j)) If Find_tree(u)<>Find_tree(V) then T:=T U Q[j]; Union(u,v;)
|
|