Xây dựng cây khung bé nhất của đồ thị liên thông được cho bởi danh sách cạnh theo thuật toán Kruskal:
T[1..n-1] of Edge;

1. Sắp xếp các danh sách cạnh sao cho:
ds[1].t ≤ ds[2].t ≤	...≤ ds[m].t
2. For i:=1 to n do	VT(i):=i;
3. k=0; ts:=0;
4. For j=1 to m do
		If VT(ds[j].d) !=		VT(ds[j].c) Then
			a. k++;
			T[k] := ds[j];
			ts:=ts + ds[j];
			b. tgd:= VT(ds[j].d);
			tgc:= VT(ds[j].c);
			for i:= 1 to n do
					If VT(i) := tgd Then VT(i):=tgc;
5. output T, m

việc chọn cạnh đưa vào cây khung chỉ việc lấy từ trên xuống dưới (sau khi đã sắp xếp theo trọng số tăng dần) sao cho chúng không tạo thành chu trình. Ta sẽ giải quyết vấn đề làm thế nào để kiểm tra cây khung có tạo thành chu trình khi thêm 1 cạnh vào không.
Tại mỗi bước ta có T là tập các cây khác nhau, nếu cạnh thêm vào có điểm đầu và điểm cuối cùng thuộc một cây thì chúng tạo thành chu trình. ta sẽ dùng mảng VT để đánh dấu đỉnh thuộc cây nào. Lúc đầu VT[i] = 0 với mọi i, tức là đỉnh chưa thuộc cây nào trong T.
khi xét đến cạnh (d,c) sẽ xảy ra các TH sau:
1. VT[d] = 0 & VT[c] = 0 → cả 2 đỉnh đều chưa thuộc cây nào trong T, tạo ra cây mới chứa cạnh này.
2. VT[d] = 0 & VT[c] ≠ 0: cho cạnh vào T, gán lại VT[c] = VT[d];
3. VT[d] ≠ 0 & VT[c] = 0: tương tự 2
4. VT[d] ≠ VT[c] và cả 2 ≠ 0: 2 đỉnh đang thuộc 2 cây khác nhau: cho cạnh vào T, hợp nhất 2 cây bằng cách gán VT của các đỉnh của 1 cây = VT đỉnh cây còn lại
5. VT[d]= VT[c] ≠ 0: 2 đỉnh này thuộc cùng 1 cây trong T, nếu cho vào tạo thành chu trình → bỏ qua.

Tôi viết giả mã dựa trên ý tưởng đó, có thể chưa tinh, các đ/c cho ý kiến nhé.
proc KRUSKAL()
1. Sắp xếp các cạnh sao cho:
ds[1].t ≤ ds[2].t ≤....≤ ds[m].t;
2. FOR j := 1 TO n DO VT[j] := 0;
3. //cho cạnh đầu tiên vào T, gán chỉ số cây 2 đỉnh của cạnh là 1
k := 1, t := 1 //k: số các cạnh có trong T, t: số các cây có trong T
VT[ds[1].d] := t; VT[ds[1].c] := t;
E'[k] =ds[1]; m = ds[1].t ;
i:= 2;
4. WHILE k ≤ n -1 DO
          di := ds[i].d; ci := ds[i].c;// cho viết đoạn sau nó gọn thôi, k có mục đích gì khác
          IF (VT[di] ≠ 0 & VT[di] = VT[ci]) THEN // k làm gì cả
          ELSE
                    IF ( VT[di] + VT[ci] = 0) THEN //2 dinh chua Э cay nao
                              t++;
                              VT[di] := t; VT[ci] := t;
                    ELSE
                              IF (VT[di] = 0) THEN
                                        VT[di] := VT[ci];
                              ELSE IF (VT[di] = 0) THEN
                                        VT[ci] := VT[di];
                              ELSE // VT[di] ≠ VT[ci] và đều ≠ 0
                              // gán lại VT của cây chứa đỉnh đầu = VT của cây chứa đỉnh cuối
                              temp:= VT[di];
                              FOR s := 1 TO n DO
                                        IF (VT[s] = temp) THEN VT[s]: = VT[ci];
                    //thêm cạnh vào T:
                    k := k+1;
                    E’[k] := ds[i]; m = m + ds[i].t;
          i++;

Hi, ý tưởng thuật toán của em cũng tương tự của anh, chỉ khác cách đánh dấu đỉnh thuộc cây nào là khác chút thôi: anh khởi tạo n cây khác nhau rồi xét 2 đỉnh không thuộc cùng 1 cây thì cho cạnh vào T và hợp 2 cây lại. cách viết của anh gọn hơn :)

Không biết mọi người nghĩ về ý tưởng trên như thế nào. Nhưng cá nhân tôi thấy phức tập quá. Tôi chỉ cần 3,4 dòng lệnh là xong việc kiểm tra khi thêm một cạnh nó có tạo thành chu trình hay không? Mọi người nghĩ tiếp nha.

Xây dựng cây khung bé nhất của đồ thị liên thông được cho bởi danh sách cạnh theo thuật toán Kruskal:
T[1..n-1] of Edge;
Bình luận một chút lời giải của LĐS. Đang đánh dở dang, mất điện lại phải gõ lại.
1. Sắp xếp các danh sách cạnh sao cho:
ds[1].t ≤ ds[2].t ≤...≤ ds[m].t
Cái này theo đúng kiểu của thầy, đã hiểu, khỏi bình luận vì đã nói kỹ trong [You must be registered and logged in to see this link.]
2. For i:=1 to n do VT(i):=i; Đánh dấu tất cả các đỉnh bằng số thứ tự đỉnh, cái này khác với Prim là đánh dấu 0 toàn bộ.
3. k=0; ts:=0; Khởi tạo giá trị đầu. k là số thứ tự cạnh của cây T, còn ts là tổng số độ dài của cây.
4. For j=1 to m do Kiểm tra lần lượt m cạnh hiện có của đồ thị G.
If VT(ds[j].d) != VT(ds[j].c) Then Nếu hai đầu của cạnh hiện tại đánh dấu không giống nhau: Thực hiện 1 loạt việc:
a. Các công việc để thêm cạnh hiện tại vào cây khung gồm:
k ++ Tăng biến đếm cạnh hiện tại của cây khung lên.
T[k] := ds[j]; Lấy cạnh hiện tại của G đưa vào cạnh của cây khung.
ts:=ts + ds[j]; Đo độ dài của cây khung bằng cách công thêm cạnh hiện tại vừa thêm vào.
b.Các công việc để đánh dấu lại
tgd:= VT(ds[j].d); Ghi lại giá trị đánh dấu của đỉnh đầu cạnh đang xét
tgc:= VT(ds[j].c); Ghi lại giá trị đánh dấu của đỉnh cuối cạnh đang xét
for i:= 1 to n do Kiểm tra lần lượt các đỉnh:
If VT(i) := tgd Then VT(i):=tgc; Nêu đỉnh đầu nào mà có đánh dấu giống như giá trị lưu trong tgd thì thay giá trị đánh dấu bằng giá trị lưu trong tgc. Điều này nghĩa là sẽ đồng nhất các đỉnh đã nối sẽ cùng đánh dấu một giá trị. Khi đó những đỉnh đã nối vào với nhau sẽ không nối nội bộ được nữa, điều này sẽ khiến không thể tạo thành chu trình bởi dòng lệnh
If VT(ds[j].d) != VT(ds[j].c) chỉ cho phép nối các đỉnh có đánh dấu khác nhau.
5. output T, m

Nhận xét:
Có tạo thành cây khung không? Có vì tạo thành khi đã đánh dấu các đỉnh đã có cạnh cùng một giá trị.
Có nên duyệt hết tất cả các cạnh không?
Giả sử: có đồ thị G và cây khung như bên dưới đây:
[You must be registered and logged in to see this image.]
Có 5 đỉnh, 10 cạnh. Sao không đếm đủ số cạnh = 4 thì thôi luôn, mà lại cứ phải tìm hết 10 cạnh, thực chất là việc tìm cho đủ số cạnh là không cần thiết, sau khi đã kiếm đủ 4 cạnh rồi. Các bạn nhìn xem, nếu số đỉnh là 100, số cạnh có thể rất lớn... nếu như tất cả các đỉnh được nối với nhau?

- Đ/c Admin sửa sai cấu trúc của đ/c Son rồi.

câu lệnh
for i:= 1 to n do If VT(i) := tgd Then VT(i):=tgc; phải nằm trong dòng lệnh (b) nhé.



- Trong trường hợp cạnh thưa, thì việc duyệt cạnh theo như đ/c Son For j=1 to m do .... là tương đối tốt(thủ tục Viết lại 2 - trang 116). Nếu sử dụng vòng while k < n-1(thủ tục Viết lại 1 - trang 116) thì mỗi một giá trị k, ta phải duyệt lại cạnh từ đầu.
- Trong trường hợp nhiều cạnh như ví dụ đ/c Admin đưa ra thì sử dụng while k < n-1 sẽ tốt hơn. Nhưng nếu trọng số bằng nhau hết thì có khi cũng phải duyệt hết, chẳng bỏ được cạnh nào.

Việc bây giờ là các anh chị cần giải thêm với cấu trúc dữ liệu cho dưới dạng ma trận kề và cho bởi danh sách liên kết. Em nghĩ nếu không nghĩ cách viết thủ tục riêng để gọi vào thì cũng tương đối rắc rối, ở chỗ rất dễ nhầm lẫn.

Tongmanhcuong đã viết:Không biết mọi người nghĩ về ý tưởng trên như thế nào. Nhưng cá nhân tôi thấy phức tập quá. Tôi chỉ cần 3,4 dòng lệnh là xong việc kiểm tra khi thêm một cạnh nó có tạo thành chu trình hay không? Mọi người nghĩ tiếp nha.

cả 2 ý tưởng trên đều giống thuật toán thầy giảng, a có ý tưởng hay hơn, sao k trình bày với thầy xem thầy nghĩ sao.

Tôi sửa lại bài viết cho giống cách viết của thầy:
cách 1:
proc KRUSKAL()

1) Sắp xếp ds[1].t ≤ ds[2].t ≤ ....≤ ds[m].t;

2) FOR x := 1 TO n DO sh[x] := 0;

3) //cho cạnh đầu tiên vào T, gán chỉ số cây 2 đỉnh của cạnh là 1
k := 1, s := 1 //k: số các cạnh có trong T, s: số hiệu cây
sh[ds[1].d] := s; sh[ds[1].c] := s;
E'[k] = ds[1]; ts = ds[1].t ;
j := 2;

4) WHILE k ≤ n -1 DO
{
          WHILE (sh[ds[j].d] = sh[ds[j].c] & sh[ds[j].c] ≠ 0) j++;
d := ds[i].d; c := ds[i].c;// cho viết đoạn sau nó gọn thôi, k có mục đích gì khác
p := sh(d); q := sh(c);
          IF (p = q ) THEN
                    s := s + 1;
                    sh(d) := s; sh(c) := s;
          ELSE
                    a) t := p; IF q > 0 THEN t := q;
                    b) IF (p.q = 0)THEN
                              sh(d) := t; sh(c) := t;
                    ELSE
                              FOR x := 1 TO n DO
                                        IF(sh(x) = p || sh(x) = q) THEN sh(x) := t;
//thêm cạnh vào T:
          k := k + 1;
          E’[k] := ds[j]; ts= ts + ds[j].t;
          j:= j + 1;
}
5) output E', ts

cách 2: Ban đầu đánh số mỗi đỉnh là một cây

proc KRUSKAL()

1) Sắp xếp ds[1].t ≤ ds[2].t ≤....≤ ds[m].t;

2) FOR x := 1 TO n DO sh[x] := x;

3) k := 0; ts := 0; j := 1;

4) WHILE k ≤ n - 1 DO
{
          WHILE ( sh[ds[j].d] = sh[ds[j].c] ) DO j++;
d := ds[i].d; c := ds[i].c;// cho viết đoạn sau nó gọn thôi, k có mục đích gì khác
p := sh(d); q := sh(c);

FOR x := 1 TO n DO
          IF(sh(x) = p) THEN sh(x) := q;

//thêm cạnh vào T:
k := k + 1;
E’[k] := ds[j]; ts = ts + ds[j].t;
j := j + 1;
}

5. output E', ts

mrP đã viết:- Đ/c Admin sửa sai cấu trúc của đ/c Son rồi.

câu lệnh
for i:= 1 to n do If VT(i) := tgd Then VT(i):=tgc; phải nằm trong dòng lệnh (b) nhé.

- Trong trường hợp cạnh thưa, thì việc duyệt cạnh theo như đ/c Son For j=1 to m do .... là tương đối tốt(thủ tục Viết lại 2 - trang 116). Nếu sử dụng vòng while k < n-1(thủ tục Viết lại 1 - trang 116) thì mỗi một giá trị k, ta phải duyệt lại cạnh từ đầu.
- Trong trường hợp nhiều cạnh như ví dụ đ/c Admin đưa ra thì sử dụng while k < n-1 sẽ tốt hơn. Nhưng nếu trọng số bằng nhau hết thì có khi cũng phải duyệt hết, chẳng bỏ được cạnh nào.

đ/c Phương có chút nhầm lẫn nha, đối với thuật toán Kruskal, luôn duyệt các cạnh từ trên xuống theo danh sách đã sắp xếp, nên k có chuyện duyệt lại từ đầu (j=2 ở ngoài vòng while)

- Nhầm lẫn là do thứ 6 ở nhà ngủ. Bài viết đấy viết trước khi thầy làm mẫu thuật toán Kruskal, tớ trích dẫn thuật toán trên là trong sách của thầy (tớ đã ghi là Viết lại 1/ trang 116 rồi mừ )- thế mà còn chém mình. Còn cách mọi người làm bây giờ là có cải tiến chút ít nên không cần duyệt lại từ đầu. OK.

- Nếu xem xét lại thuật toán mới của thầy thì đúng là tối ưu hơn cả. Vì trong cả hai cách nếu sh[ds[j].d] = sh[ds[j].c] thì chỉ thực hiện j++, còn nếu khác nhau thì gán vào E[k+1], tăng ts. Trong trường hợp xấu nhất, tức là cả hai đều xét hết các cạnh thì rõ ràng số bước thực hiện là như nhau. Còn bình thường nếu duyệt theo cạnh i:=1 to m thì khi k=n-1 rồi, nó vẫn bắt buộc thực hiện tiếp lệnh j++ cho đến khi duyệt hết cạnh.

- Spam, câu view tí...
         

- Nhân tiện nhờ em Hiền xem hộ bài này nhé : [You must be registered and logged in to see this link.]

Nếu đề ra như sau:
Đồ thị G liên thông n đỉnh được đánh số từ 1 đến n nhưng được cho bởi ma trận trọng số A = (a_ij) viết thủ tục xây dựng cây khung bé nhất?
Ta vẫn làm như vậy nha. Thử xem nào.
Bước đầu tiên bao giờ cũng phải là mô tả cấu trúc cây khung. Bỏ bước này trừ một nửa số điểm.
T : ARRAY (1.. n-1) of Cạnh
          Cạnh = record
          d, c: tên đỉnh;
          end;

Bước thứ 2 viết một số thủ tục nho nhỏ nếu có để tiện sử dụng. Việc viết này giúp ta không phải viết đi viết lại một đoạn mã.
Ví dụ

Code:

FUNC ChonDuoc (i, j: tên đỉnh): Boolean
ChonDuoc = c(i) ≠ c(j)


Bước 3. Chọn một thuật toán để viết.

Viết bằng thuật toán Kruskal:

Viết bằng thuật toán Prim: