Nháy vào khung màu hồng này để hiện, ẩn:

Nháy vào chỗ hồng hồng này để ẩn hiện: :

Nháy vào đây để ẩn/hiện chương trình chuẩn tối ưu có công của cả 3 chuyên gia:

haihonglyk6 đã viết:ở phần 4 của Hiền nên sửa lại thế này hay hơn
4. while (k< n-1)
{
j:=2;(sau mỗi lần thêm được 1 cạnh lại phải xét lại từ pt thứ 2)
while (VT[ds[j].d] = VT[ds[j].c]) j=j+1
k++;
E'[k]:= ds[j]; m = m + ds[j].t;
VT[ds[j].d]:=1; VT[ds[j].c]:=1;
}

mrP đã viết:Giải thuật PRIM, biết ma trận kề, trọng số D[i,j]. Nếu đỉnh i không nối với đỉnh j thì D[i,j]=+∞.

Tongmanhcuong đã viết:Tôi rất vui khi một số thành viên có quan điểm giống tôi (Luôn luôn cố gắng để có được sản phẩm tốt). Nguyện theo nguyện vọng của anh Admin, tôi Post lên. Có gì góp ý nha. Bài của tôi là trường hợp Tổng quát.
Thank Mrs Hồng for giving a happy.



1) Sắp xếp danh sách Ds không giảm theo trường t (trọng số);

For i:= 1 To n Do Chưa_xét[i]:= 0;

k:= 1; E[k]:= Ds[1]; ts:= E[k].t;

Chưa_xét[E[k].d]:=1; Chưa_xét[E[k].c]:=1;

j:=1;

2) While j <= m Do

          j:= j + 1;

          If (Chưa_xet[Ds[j].d]<>Chưa_xét[Ds[j].c]) Then

                    k:=k+1;

                    E[k]:=Ds[j]

                    Chưa_xét[E[k].d]:= 1; Chưa_xét[E[k].c]:=1;

                    ts:= ts+ E[k].t;

          If k=n-1 Then Break Else j:=1;

3) If k < n-1 Then Output “Đồ thị không liên thông”

Else Output ts, E;


Anh Admin chỉnh lại cho đúng Hàng cột nhé.

Về viết lệnh:

Admin đã viết:

Về viết lệnh:

Áp dụng thuật toán để tìm cây khung bé nhất của đồ thị G vô hướng sau:

1, 2, 3 2, 3, 3 1, 6, 2 2, 7, 1 3, 8, 4

5, 1, 3 6, 2, 2 7, 3, 5 8, 4, 2 5, 6, 4

9, 5, 1 10, 6, 3 6, 11, 3 6, 7, 4 11, 7, 2

7, 12, 2 12, 8, 2 9, 10, 4 10, 11, 4 11, 12, 5

3, 4, 4 5, 10, 4 7, 8, 2 4, 1, 7 12, 9, 2

Đầu tiên xếp theo thứ tự trọng số các cạnh tăng dần:

TT	đầu	cuối	trọng số
1	2	7	1
2	9	5	1
3	1	6	2
4	6	2	2
5	8	4	2
6	11	7	2
7	7	12	2
8	12	8	2
9	7	8	2
10	12	9	2
11	1	2	3
12	2	3	3
13	5	1	3
14	10	6	3
15	6	11	3
16	3	8	4
17	5	6	4
18	6	7	4
19	9	10	4
20	10	11	4
21	3	4	4
22	5	10	4
23	7	3	5
24	11	12	5
25	4	1	7

Cứ lấy từ trên xuống, cạnh nào mà tạo chu trình thì không lấy, đánh dấu vào bảng đỉnh. Bao giờ lấy đủ 12 đỉnh thì dừng lại. Ở đây đánh thứ tự lấy từng đỉnh, từng dòng để dễ quan sát và trình bày. Cột số thứ tự bên trái để thangbom dễ đối chiếu với bảng trên ở thứ tự cạnh đã sắp xếp.
[You must be registered and logged in to see this image.]

Admin đã viết:Chương trình giả mã của Hà Thị có thể trình bày lại theo đúng dạng mẫu của thầy, như sau:

Nháy vào khung màu hồng này để hiện, ẩn:

Để làm rõ từng dòng lệnh, ta sẽ xem xét căn cứ vào thực tế nha.
1. Đầu tiên đề bài cho cấu trúc dữ liệu được lưu trữ dưới dạng record có tên là DS. Nó có 3 trường gồm d: đỉnh đầu, c: đỉnh cuối và t là trọng số. Khi sắp xếp ds[1].t <= ds[2].t<=...<= ds[m].t có nghĩa là sắp trọng số tăng dần. Quá dễ hiểu, thôi đoạn này bỏ qua nha.
2. Tiếp theo đoạn: FOR i:=1 to n rồi đặt VT[i]:=0; là Hà Thị đã reset đặt lại tất cả cái mảng theo dõi trạng thái của các đỉnh về 0. Uh, lẽ ra đặt tên dễ gợi nhớ đi 1 chút thì khó quên hơn, ví dụ như TD là theo dõi chẳng hạn. Thôi, không sao, VT thì VT. Nhớ VT là theo dõi đó nhen, i là đỉnh thứ mấy đó.
3. Dòng này đặt k = 1 để đánh dấu rằng, bắt đầu lấy cạnh đầu tiên, k này vừa là số thứ tự, vừa là cạnh thứ mấy đó nhen.
Đặt E'[k]=ds[1]; nghĩa là cạnh thứ k (vừa gán = 1 ở trên) bằng cạnh 1 trong danh sách ds. Đã đặt cả cạnh là 2 đầu mút rồi, Mrp nói cần đánh dấu 2 đỉnh này, nên cần thêm dòng đánh dấu 1 đầu này, T[ds[1].d]:=1; VT[ds[1].c]:=1;. quên đánh dấu 2 đỉnh này sẽ bị biến thành chu trình phần sau, OK.
Đặt m= m+ ds[1].t; là nàng đo độ dài của cạnh thứ nhất (lấy trọng số ds[1].t), đưa vào tổng độ dài của cây khung. Việc đặt tên biến cũng không được rõ ràng tường minh cho lắm, ví dụ đặt là daick (dài cây khung chẳng hạn) thì có lẽ dễ theo dõi hơn. Nhưng thôi, bỏ qua tiểu tiết, nhớ là m là đo độ dài cây khung đó nhen.
4. WHILE (k< n-1) do: Câu này quá dễ, chừng nào cây khung chưa đủ số cạnh = n-1 thì quyết kiếm cho đủ ! Tạm gọi vòng lặp này là vòng kiếm đủ số cạnh cho cây khung.
j:=2 Xét từ cặp thứ 2: Rất khôn. Xem bình luận dưới.
stop:= false; khởi tạo biến cờ, không có thôi gì cả, bao giờ xong, báo thôi thì mới thôi. Biến này dùng cho vòng FOR ở trong.
WHILE (!stop) do: Chừng nào chưa thôi thì cứ làm! Tạm gọi vòng này là vòng kiếm cho được 1 cạnh mới thôi.
if (VT[ds[j].d] != VT[ds[j].c]]) THEN Nếu đỉnh đầu và đỉnh cuối của phần tử thứ j trong danh sách, đánh dấu khác nhau thì:
k++ đếm luôn: thêm 1 đỉnh
E'[k]:= ds[j]; Cạnh thứ k bằng phần tử thứ j trong (danh sách cạnh đã sắp xếp ở đầu rồi)
m = m + ds[j].t; Đo luôn trọng số, đưa vào độ dài cây khung.
VT[ds[j].d]:=1; VT[ds[j].c]] = 1: Đánh dấu luôn 2 đỉnh này là 1.
Chả sao cả, vì chẳng biết được đỉnh nào chưa đánh dấu, nếu nó đã được đánh dấu là 1 ở vòng trước rồi thì đánh lại chẳng sao, đỡ phải kiểm tra. Lưu ý là bên trên đã If (VT[ds[j].d] != VT[ds[j].c]]) có nghĩa là kiểm tra một đỉnh đã có dấu (1) và một đỉnh chưa có dấu (0) mới làm các bước trên. Ở đây không phải xét lung tung mà bản chất là xét phần tử thứ j của danh sách cạnh đã sắp xếp, xét 2 đỉnh đầu cuối của nó.
stop = true: Đặt biến cờ cho vòng lặp này thôi. Nghĩa là đặt được thì thôi luôn, còn chưa đặt được thì xét cặp đỉnh khác.
ELSE j++ Còn trường hợp khác, tăng j lên để xét phần tử kế tiếp trong danh sách cạnh đã sắp xếp.
Thoát khỏi vòng lặp kiếm 1 cạnh, quay lại đầu vòng lặp kiếm đủ số cạnh, thấy ngay j: = 2, nhiều người bỏ quên cái câu j = 2 là chết oan ngay, vì phải xét lại từ đầu danh sách, để tránh bỏ sót. Khi làm bằng tay, ta để ý là có chỗ nhảy cách xuống phần kế danh sách, mà bên trên có phần tử lúc ý chưa thoả mãn, nhưng bây giờ nó mới thoả mãn thì ta lại lấy vào. Nghĩa là luôn luôn xét từ đầu danh sách, mỗi khi lấy xong một cạnh.
5. Xong thì đưa nó ra bằng output, đưa ra các cạnh của cây khung E' và độ dài của cả cây khung m.
Khách viếng thăm xem lại bình luận xem có cần thiết phải bổ sung không nha!
[You must be registered and logged in to see this link.]

hienha đã viết:

Tongmanhcuong đã viết:Tôi rất vui khi một số thành viên có quan điểm giống tôi (Luôn luôn cố gắng để có được sản phẩm tốt). Nguyện theo nguyện vọng của anh Admin, tôi Post lên. Có gì góp ý nha. Bài của tôi là trường hợp Tổng quát.
Thank Mrs Hồng FOR giving a happy.



1) Sắp xếp danh sách Ds không giảm theo trường t (trọng số);

FOR i:= 1 To n Do Chưa_xét[i]:= 0;

k:= 1; E[k]:= Ds[1]; ts:= E[k].t;

Chưa_xét[E[k].d]:=1; Chưa_xét[E[k].c]:=1;

j:=1;

2) WHILE j <= m Do

          j:= j + 1;

          If (Chưa_xet[Ds[j].d]<>Chưa_xét[Ds[j].c]) THEN

                    k:=k+1;

                    E[k]:=Ds[j]

                    Chưa_xét[E[k].d]:= 1; Chưa_xét[E[k].c]:=1;

                    ts:= ts+ E[k].t;

          If k=n-1 THEN Break ELSE j:=1;

3) If k < n-1 THEN Output “Đồ thị không liên thông”

ELSE Output ts, E;


Anh Admin chỉnh lại cho đúng Hàng cột nhé.

1. Vòng lặp WHILE chỉ có thể đặt j < m. Nếu có dấu '='. khi j=m, vẫn thỏa mãn → j = j+1 = m+1 sẽ báo lỗi ở dòng lệnh Ds[j] tiếp theo
2. Nếu đã đặt biến có ý nghĩa thì anh nên thay Chưa_xét = Đã_xét :)