Đáp án bài tập lý thuyết đồ thị đây

hự hự. môn này chuối thế t chưa được chữ nào. chết mất

uhm có thể bỏ qua khuyên vậy thì cạnh 2,3 có trọng số là bn nhỉ

[C++] Cây khung nhỏ nhất – Thuật toán Prim

Đề bài

Cho G=(X,E) là một đồ thị liên thông có trọng số gồm n đỉnh. Thuật toán Prim được dùng để tìm ra cây khung nhỏ nhất của G.

Thuật toán prim

Bước 1: Chọn tùy ý v thuộc X và khởi tạo Y:= {v}; T := Ø. Trong đó X là tập các đỉnh của đồ thị, Y là tập các đỉnh được chọn vào cây khung nhỏ nhất và T là tập các cạnh của cây này.
Bước 2: Trong số những cạnh e nối đỉnh w với đỉnh v trong Y với w thuộc X\Y và v thuộc Y ta chọn cạnh có trọng lượng nhỏ nhất.
Bước 3: Gán Y := Y thuộc {w} và T:= T thuộc {e}
Bước 4: Nếu T đủ n – 1 phần tử thì dừng, ngược lại làm tiếp tục bước 2.
Chú ý: trong các thuật toán tìm khung nhỏ nhất chúng ta có thể bỏ đi hướng các cạnh và các khuyên; đối với cạnh song song thì có thể bỏ đi và chỉ để lại một cạnh trọng lượng nhỏ nhất trong chúng.

Thuật toán code trong source

Thứ 1:

Xét xem trong ds các đỉnh liên thông có từ 2 đỉnh trở lên ko?

Chỉ có 1 thì không cần phải xét tiếp phần sau.

Còn có từ 2 đỉnh trở lên sẽ qua bước thứ 2

Thứ 2:

Tạo 2 danh sách: ds đỉnh chưa xét và ds đỉnh đã xét

Do biết chắc đỉnh liên thông từ 2 đỉnh trở lên nên lấy ngẫu nhiên 1 đỉnh tùy ý trong ds đỉnh liên thông vì thế trong đoạn code lấy đại đỉnh đầu tiên ứng với chỉ số 0.

Như vậy: ds đỉnh đã xét ban đầu có 1 đỉnh. Ds đỉnh chưa xét sẽ là các đỉnh còn lại nằm trong ds đỉnh liên thông

Kế đến thực hiện vòng lặp.

B1: xác định lặp khi nào đỉnh chưa xét vẫn còn thì tiếp tục lặp

B2: Thực hiện tìm cạnh có trọng số nhỏ nhất

B2a: Lấy từng đỉnh của ds đã xét, kết với từng đỉnh trong ds chưa xét.

B2b: nếu như 2 đỉnh có nối lại trực tiếp (dựa vào ma trận) thì lấy cạnh đó ra

B2c: lấy cạnh vừa rồi so với các cạnh còn lại mà chưa được nối (từ ds đỉnh đã xét với đỉnh chưa xét)

B3: sau khi đã tìm được cạnh có trọng số nhỏ nhất thì đưa cạnh đó vào dscanh của class cây khung.

Thực hiện như vậy cho đến khi hết lặp, có nghĩa là hết danh sách đỉnh chưa xét

Các bạn chú ý: trong các thuật toán tìm khung nhỏ nhất chúng ta có thể bỏ đi hướng các cạnh và các khuyên; đối với cạnh song song thì có thể bỏ đi và chỉ để lại một cạnh trọng lượng nhỏ nhất trong chúng.

Như vậy đề bài 1 mà cô đưa ra có cạnh (2 , 2) 3 thì ta coi nó như không có khuyên có phải không nhỉ?

phuonghoa_91 đã viết:

uhm có thể bỏ qua khuyên vậy thì cạnh 2,3 có trọng số là bn nhỉ

không cho thì không có cạnh đó chứ. Hehe

uhm nói chung có cạnh đấy hay ko thì không ảnh hưởng tới kq..tớ làm ra là như vậy:)

phuonghoa_91 đã viết:

uhm nói chung có cạnh đấy hay ko thì không ảnh hưởng tới kq..tớ làm ra là như vậy:)

"có" với "không có" nó khác nhau chứ!

vboy_namioz19 đã viết:

phuonghoa_91 đã viết:

uhm nói chung có cạnh đấy hay ko thì không ảnh hưởng tới kq..tớ làm ra là như vậy:)

"có" với "không có" nó khác nhau chứ!

uhm có khác nhau..thì tớ không đi dường đó quay lại đi lối khác nhưng cái chính là kq vẫn không lệch..may thế

cạnh đó là (2,3,3) mà các bạn

Hero_Kid đã viết:

cạnh đó là (2,3,3) mà các bạn

Hôm đó anh em có thắc mắc nhưng cô không sửa chứng tỏ có cạnh (2 2 3). Mà hem có cạnh (2, 3, 3) đâu nhé!

Thành ơi!!hình như chép sai đề!!cạnh (6,11,3) chứ đâu phải (6,11,4)

t nghĩ là cạnh 2,2,3 đấy. lúc hỏi mà cô cũng có chữa lại đâu, cô cười bảo là cứ làm đi mà

nếu là 2,2,3 thì t ra trọng số bằng 23 còn 2,3,3 là 22. bài của Thành câu 4 làm gì có cạnh u,f nhỉ?

còn ai chưa nộp bài ko?