Bạn Khách viếng thăm thân!
Xem xét một cách toàn diện thì đề thi về CTDL và GT thường rất dài. Nghĩa là khi vào thi mà Khách viếng thăm không cắm cúi viết liên tục từ đầu đến cuối thì có lẽ chẳng thể kịp thời gian. Có nghĩa là Khách viếng thăm có tài giỏi đến mấy mà không chịu học thuộc thì không thể có điểm cao được.

Các đề thi trong 1 câu thường có 1 phần là yêu cầu Khách viếng thăm phải biểu diễn bằng tay từng bước một công việc nào đấy. Việc biểu diễn duyệt đồ thị cũng hay được yêu cầu trên các đề thi. Việc này cần thực hiện và trình bày thì Khách viếng thăm phải làm như thế nào?

Ví dụ:
Đề sẽ cho 1 đồ thị. Nếu họ vẽ ra, thì sẽ yêu cầu Khách viếng thăm viết một ma trận kề, hoặc danh sách kề. Hoặc ngược lại, nếu đề ra một ma trận kề, hoặc danh sách kề thì Khách viếng thăm phải vẽ được đồ thị ra. Việc này rất quan trọng, nó quyết định rằng Khách viếng thăm có làm đúng hay làm sai và có được điểm hay không?

Giả sử có danh sách kề như sau:

v	Kề của v
a	b, c, d, e
b	a, d
c	a, e, g
d	b, a, e
e	d, f, g, c, a
f	e, g
g	e, c, f

Bây giờ đề bài yêu cầu chúng ta mô tả việc duyệt theo chiều sâu thì phải làm thế nào?

Đầu tiên, bản chất của việc duyệt theo chiều sâu là gì? Giả sử duyệt từ đỉnh a, thì hãy coi đỉnh a như là gốc. Nguyên tắc duyệt là chạy nhanh càng xa khỏi gốc trước, duyệt từ xa, sau đó với co dần lại. Ngược lại, với duyệt theo chiều rộng thì duyệt hết những đình kề hiện tại, rồi mới duyệt các đỉnh xa hơn.

Duyệt theo chiều sâu sử dụng đệ quy, còn duyệt theo chiều rộng, sử dụng hàng đợi.

Thôi cố đọc sách của thầy Đỗ Xuân Lôi, mua ở cửa hàng sách cũ khoảng 10.000 - 15.000 cuốn, sẽ hiểu hết mà. Hoặc thích đọc qua máy tính thì [You must be registered and logged in to see this link.].

Cách làm:
1. Vẽ lại bảng danh sách kề vào bài thi
2. Đánh các số be bé giống như luỹ thừa vào các đỉnh. Đây là thứ tự duyệt.
3. Nhớ đánh dấu các đỉnh đã duyệt để tránh duyệt nhầm vào đỉnh đã duyệt rồi.
4. Ghi xuống 1 dòng cuối bảng thứ tự các đỉnh đã duyệt.

Bài trên làm thế nào?
Xem cách trình bày đây sẽ hiểu.

Duyệt theo chiều sâu, bắt đầu từ đỉnh a.

Dấu	v	Kề của v
x	a1	b2, c, d, e
x	b	a, d3
x	c	a, e, g
x	d	b, a, e4
x	e	d, f5, g, c, a
x	f	e, g6
x	g	e, c7, f

Thứ tự:
a, b, d, e, f , g, c
Bây giờ Khách viếng thăm cần chia sẻ cùng mọi người đi!

Bây giờ cần trình bày duyệt tay theo chiều rộng xuất phát từ a thì làm thế nào vào bài thi?
Kẻ lại cái bảng ra, có cột để đánh dấu, cũng đánh thứ tự như cái bảng duyệt chiều sâu nhé!
Phía dưới bảng ghi 2 dòng:
Dòng 1, ghi thứ tự của hàng đợi.
Dòng 2, ghi kết quả.

Làm như vầy:

Dấu	v	Kề của v
x	a1	b2, d3, e4, c5
x	b	a, d
x	c	a, e, g
x	d	b, a, e
x	e	d, f6, g7, c, a
x	f	e, g
x	g	e, c, f

Hàng đợi: a, b, d, e, c, f, g
Kết quả: a, b, d, e, c, f, g

Cho đồ thị G {V, E} có n đỉnh 1-n. Cho bởi danh sách cạnh.
DS [1..m] of cạnh
          cạnh = record
                    đ,c : tên đỉnh;
                    t: trọng số;
          end;

a. Viết thủ tục tìm cây khung bé nhất theo thuật toán Prim.
b. Áp dụng tính bằng tay với các dữ liệu sau:

Đỉnh
Đầu	Cuối	Trọng số
a	b	5
b	c	4
b	d	2
a	m	3
f	e	6
d	e	3
d	f	4
d	b	5
d	c	2
a	f	7
b	n	6
n	c	7
c	m	4
d	n	2
m	e	4
f	m	4
a	n	5
a	c	2
f	c	1
b	e	2
e	c	2

Cách thực hiện bài này như thế nào?

a. Việc viết thủ tục tính cây khung bé nhất xem [You must be registered and logged in to see this link.]
b. Các bước cần thực hiện bằng tay như sau:
Bước 1. Viết lại bảng dữ liệu trên bằng cách sắp xếp trọng số tăng dần.
Ta có bảng dữ liệu B1 đã viết lại, có thêm cột k cuối cùng để ghi lại các bước cần xem xét.

Đỉnh
Đầu	Cuối	Trọng số	k
f	c	1
b	d	2
d	c	2
d	n	2
a	c	2
b	e	2
e	c	2
a	m	3
d	e	3
b	c	4
d	f	4
c	m	4
m	e	4
f	m	4
a	b	5
d	b	5
a	n	5
f	e	6
b	n	6
a	f	7
n	c	7

Bước 2. Tiếp theo, kẻ một bảng theo dõi B2, để đánh dấu như sau:

V	a	b	c	d	e	f	m	n
VT

Bước 3. Xét trong danh sách từ trên xuống của bảng B1 chọn cạnh có trọng số nhỏ nhất. Đánh dấu cột k =1. Đồng thời đánh dấu x vào bảng B2 dòng VT những đỉnh đã duyệt.

Bước 4. Thực hiện duyệt từ trên xuống, bảng B1, những dòng nào còn trống của cột k thì kiểm tra ở bảng B2 xem có đáp ứng được một đình đã có trong VT, còn đỉnh kia chưa có trong VT không. Nếu đáp ứng được thì đánh dấu lại giá trị k ++ vào cột k của B1 và đánh dấu x vào bảng B2 dòng VT đỉnh đã duyệt.

Bước 5. Ghi kết quả:
Ghi theo thứ tự của cột k các cạnh. Đồng thời tính độ lớn của cây khung bằng tổng các trọng số.
Ví dụ sau bước 5 B1 sẽ là:

Đỉnh
Đầu	Cuối	Trọng số	k
f	c	1	1
b	d	2	3
d	c	2	2
d	n	2	4
a	c	2	6
b	e	2	5
e	c	2	≡
a	m	3	≡
d	e	3	≡
b	c	4	7
d	f	4
c	m	4
m	e	4
f	m	4
a	b	5
d	b	5
a	n	5
f	e	6
b	n	6
a	f	7
n	c	7

Ghi lại kết quả:
Cây khung: {(f, c), (d, c), (b, d), (d, n), (b, e), (a, c), (b, c)}
Tổng của các trọng số là: 14

Cám ơn anh Admin, vì em không có điều kiện đi ôn thi nên việc ôn tập cũng vất vả lắm. Tiện đây mong anh giúp em, với đồ thị cho Như trên thì việc giải tay đối với bài cây khung nhỏ nhất với thuật toán Kruskal là như thế nào ạ.

Mong anh giúp em để hiểu hơn về thuật toán này...

Ban QT: Tương tự, bằng cách copy đoạn trên ra ra bỏ bước (không kiểm tra) liên thuộc.

hi . em đoc chẳng hiểu các anh có thể viết c++ về thuật toán prim tìm cây khung nhỏ nhất được không?

Ban QT:
Ở đây trình bày để làm vào bài thi được điểm. Học về giải thuật phải viết bằng giả mã. Nếu muốn xem cụ thể thì down tài liệu trên để đọc và muốn xem viết bằng C++ thì sử dụng gooogle... Bạn không làm theo yêu cầu của đề bài sẽ được 0 điểm phần trình bày của bạn.

[quote="Admin"]Bạn Khách viếng thăm thân!
Xem xét một cách toàn diện thì đề thi về CTDL và GT thường rất dài. Nghĩa là khi vào thi mà Khách viếng thăm không cắm cúi viết liên tục từ đầu đến cuối thì có lẽ chẳng thể kịp thời gian. Có nghĩa là Khách viếng thăm có tài giỏi đến mấy mà không chịu học thuộc thì không thể có điểm cao được.

Các đề thi trong 1 câu thường có 1 phần là yêu cầu Khách viếng thăm phải biểu diễn bằng tay từng bước một công việc nào đấy. Việc biểu diễn duyệt đồ thị cũng hay được yêu cầu trên các đề thi. Việc này cần thực hiện và trình bày thì Khách viếng thăm phải làm như thế nào?

Ví dụ:
Đề sẽ cho 1 đồ thị. Nếu họ vẽ ra, thì sẽ yêu cầu Khách viếng thăm viết một ma trận kề, hoặc danh sách kề. Hoặc ngược lại, nếu đề ra một ma trận kề, hoặc danh sách kề thì Khách viếng thăm phải vẽ được đồ thị ra. Việc này rất quan trọng, nó quyết định rằng Khách viếng thăm có làm đúng hay làm sai và có được điểm hay không?

Giả sử có danh sách kề như sau:

v	Kề của v
a	b, c, d, e
b	a, d
c	a, e, g
d	b, a, e
e	d, f, g, c, a
f	e, g
g	e, c, f

Bây giờ đề bài yêu cầu chúng ta mô tả việc duyệt theo chiều sâu thì phải làm thế nào?
Duyệt theo chiều sâu :
Bắt đầu từ đỉnh a -> ta tới b ta được a,b
từ b : kiếm đỉnh kề của b không nằm khác a,b . ta đươc (d) -> a b d .
từ d : kiem dinh ke của d khong nam trong a b d .ta duoc (e) -> a b d e
tu e : kiem dinh ke cua e khong nam trong a b d e ta duoc (f) ->a b d e f
tu f : kiem dinh ke cua f khong nam trong a b d e f ta duoc (g) -> a b d e f g
tu f: kiem dinh ke cua f khong nam trong a b d e f ta duoc (c)-> a b d e f g c
Đến đây là kết thúc nha các bạn

Duyệt theo chiều rộng :
Bắt đầu từ đỉnh a, liệt kê hết các đỉnh kề của a ta được -> a b c d e
nhin vao day tren ta thay tiep theo a la b.
liet ke tap dinh cua b ma khong co trong a b c d e -> khong co dinh nao
tiep theo b la c. liet ke cac dinh cua c khong co trong a b c d e (g) -> a b c d e g
tiep theo c la d. liet ke cac dinh cua d khong co trong a b c d e g (khong co)
tiep theo d la e . liet ke cac dinh cua e khong co trong a b c d e g (f) -> a b c d e g f
Đủ các đinh thì la dừng lại -> a b c d e g f

Theo em thì kết quả bài này phải là:
(f,c); (d,c);(b,d);(d,n);(a,c);(b,e);(a,m)
Mọi người kiểm tra lại xem có đúng không ạ.

Admin đã viết:Cho đồ thị G {V, E} có n đỉnh 1-n. Cho bởi danh sách cạnh.
DS [1..m] of cạnh
          cạnh = record
                    đ,c : tên đỉnh;
                    t: trọng số;
          end;

a. Viết thủ tục tìm cây khung bé nhất theo thuật toán Prim.
b. Áp dụng tính bằng tay với các dữ liệu sau:

Đỉnh
Đầu	Cuối	Trọng số
a	b	5
b	c	4
b	d	2
a	m	3
f	e	6
d	e	3
d	f	4
d	b	5
d	c	2
a	f	7
b	n	6
n	c	7
c	m	4
d	n	2
m	e	4
f	m	4
a	n	5
a	c	2
f	c	1
b	e	2
e	c	2

Cách thực hiện bài này như thế nào?

a. Việc viết thủ tục tính cây khung bé nhất xem [You must be registered and logged in to see this link.]
b. Các bước cần thực hiện bằng tay như sau:
Bước 1. Viết lại bảng dữ liệu trên bằng cách sắp xếp trọng số tăng dần.
Ta có bảng dữ liệu B1 đã viết lại, có thêm cột k cuối cùng để ghi lại các bước cần xem xét.

Đỉnh
Đầu	Cuối	Trọng số	k
f	c	1
b	d	2
d	c	2
d	n	2
a	c	2
b	e	2
e	c	2
a	m	3
d	e	3
b	c	4
d	f	4
c	m	4
m	e	4
f	m	4
a	b	5
d	b	5
a	n	5
f	e	6
b	n	6
a	f	7
n	c	7

Bước 2. Tiếp theo, kẻ một bảng theo dõi B2, để đánh dấu như sau:

V	a	b	c	d	e	f	m	n
VT

Bước 3. Xét trong danh sách từ trên xuống của bảng B1 chọn cạnh có trọng số nhỏ nhất. Đánh dấu cột k =1. Đồng thời đánh dấu x vào bảng B2 dòng VT những đỉnh đã duyệt.

Bước 4. Thực hiện duyệt từ trên xuống, bảng B1, những dòng nào còn trống của cột k thì kiểm tra ở bảng B2 xem có đáp ứng được một đình đã có trong VT, còn đỉnh kia chưa có trong VT không. Nếu đáp ứng được thì đánh dấu lại giá trị k ++ vào cột k của B1 và đánh dấu x vào bảng B2 dòng VT đỉnh đã duyệt.

Bước 5. Ghi kết quả:
Ghi theo thứ tự của cột k các cạnh. Đồng thời tính độ lớn của cây khung bằng tổng các trọng số.
Ví dụ sau bước 5 B1 sẽ là:

Đỉnh
Đầu	Cuối	Trọng số	k
f	c	1	1
b	d	2	3
d	c	2	2
d	n	2	4
a	c	2	6
b	e	2	5
e	c	2	≡
a	m	3	≡
d	e	3	≡
b	c	4	7
d	f	4
c	m	4
m	e	4
f	m	4
a	b	5
d	b	5
a	n	5
f	e	6
b	n	6
a	f	7
n	c	7

Ghi lại kết quả:
Cây khung: {(f, c), (d, c), (b, d), (d, n), (b, e), (a, c), (b, c)}
Tổng của các trọng số là: 14