¸.•'´¯) ¸,ؤ°``°¤Ø,¸(¯`'•.¸Tin Trắc Địa k54¸.•'´¯) ¸,ؤ°``°¤Ø,¸(¯`'•.¸

¸.•'´¯) ¸,ؤ°``°¤Ø,¸(¯`'•.¸Tin Trắc Địa k54¸.•'´¯) ¸,ؤ°``°¤Ø,¸(¯`'•.¸
 
Trang ChínhCalendarGalleryTrợ giúpTìm kiếmThành viênNhómĐăng kýĐăng Nhập
Diễn đàn Tin Trắc Địa k54 đi vào hoạt động. Đây sẽ là 4rum chính thức của lớp tin trắc địa k54 - Đại học Mỏ địa chất. Tất cả thông báo tại 4rum này từ ban quản trị đều có hiệu lực trên thực tế.
Đăng Nhập
Tên truy cập:
Mật khẩu:
Đăng nhập tự động mỗi khi truy cập: 
:: Quên mật khẩu
Top posters
Cappuccino
 
vao`la`chem'
 
mr.been
 
gabong
 
vboy_namioz19
 
thank0bk54
 
chjecla_dangyeu
 
nguyenhuydung
 
phuonghoa_91
 
Hero_Kid
 
April 2018
MonTueWedThuFriSatSun
      1
2345678
9101112131415
16171819202122
23242526272829
30      
CalendarCalendar

Share | 
 

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

Go down 
Tác giảThông điệp
thank0bk54
Intel® Core 2 Duo Processor
Intel® Core 2 Duo Processor
avatar

Nam

Zodiac : Sagittarius
Chinese zodiac : Goat
Tổng số bài gửi : 97
Việt Nam đồng : 2790121
Danh Vọng : 3
Birthday : 30/11/1991

Join date : 06/10/2010
Age : 26
Đến từ : Bắc Giang
Job/hobbies : Freelancer

Bài gửiTiêu đề: Đáp án bài tập lý thuyết đồ thị đây   Tue Oct 11, 2011 9:39 pm

Phải tự mày mò nghĩ ra cách giải theo thuật toán có sẵn Kruskal và Prim làm mắt em bậy giờ hơi kèm nhèm. Bác nào copy bài làm của em nhớ trả 50 k. Oke

Bấm vào đây để tải về





Được sửa bởi thank0bk54 ngày Tue Oct 11, 2011 10:00 pm; sửa lần 1.
Về Đầu Trang Go down
hanhsn
Intel® Pentium IV Processor
Intel® Pentium IV Processor
avatar

Nữ

Zodiac : Taurus
Chinese zodiac : Goat
Tổng số bài gửi : 15
Việt Nam đồng : 2424015
Danh Vọng : 3
Birthday : 23/04/1991

Join date : 11/09/2011
Age : 27
Đến từ : Hưng Yên
Job/hobbies : Sinh Viên

Bài gửiTiêu đề: Re: Đáp án bài tập lý thuyết đồ thị đây   Tue Oct 11, 2011 9:49 pm

hự hự. môn này chuối thế t chưa được chữ nào. chết mất
Về Đầu Trang Go down
thank0bk54
Intel® Core 2 Duo Processor
Intel® Core 2 Duo Processor
avatar

Nam

Zodiac : Sagittarius
Chinese zodiac : Goat
Tổng số bài gửi : 97
Việt Nam đồng : 2790121
Danh Vọng : 3
Birthday : 30/11/1991

Join date : 06/10/2010
Age : 26
Đến từ : Bắc Giang
Job/hobbies : Freelancer

Bài gửiTiêu đề: Re: Đáp án bài tập lý thuyết đồ thị đây   Tue Oct 11, 2011 10:01 pm

thế ah
cũng bình thường mà
mỗi tỗi hơi đau mắt
Về Đầu Trang Go down
phuonghoa_91
Intel® Core 2 Duo Processor
Intel® Core 2 Duo Processor
avatar

Nữ

Zodiac : Sagittarius
Chinese zodiac : Goat
Tổng số bài gửi : 57
Việt Nam đồng : 2767057
Danh Vọng : 7
Birthday : 03/12/1991

Join date : 09/10/2010
Age : 26
Đến từ : Chương Dương, Thường Tín, Hà Nội
Job/hobbies : Discovery World

Bài gửiTiêu đề: Re: Đáp án bài tập lý thuyết đồ thị đây   Wed Oct 12, 2011 6:21 pm

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


Được sửa bởi phuonghoa_91 ngày Thu Oct 13, 2011 3:07 am; sửa lần 1.
Về Đầu Trang Go down
vboy_namioz19
Intel® Core i3 Processor
Intel® Core i3 Processor
avatar

Nam

Zodiac : Libra
Chinese zodiac : Goat
Tổng số bài gửi : 119
Việt Nam đồng : 2833118
Danh Vọng : 18
Birthday : 25/09/1991

Join date : 15/09/2010
Age : 26
Đến từ : Vinh Quang - Chiêm Hóa - Tuyên Quang
Job/hobbies : Non IT

Bài gửiTiêu đề: Re: Đáp án bài tập lý thuyết đồ thị đây   Thu Oct 13, 2011 1:37 am

[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
Về Đầu Trang Go down
http://vinhquangonline.tk/home
vboy_namioz19
Intel® Core i3 Processor
Intel® Core i3 Processor
avatar

Nam

Zodiac : Libra
Chinese zodiac : Goat
Tổng số bài gửi : 119
Việt Nam đồng : 2833118
Danh Vọng : 18
Birthday : 25/09/1991

Join date : 15/09/2010
Age : 26
Đến từ : Vinh Quang - Chiêm Hóa - Tuyên Quang
Job/hobbies : Non IT

Bài gửiTiêu đề: Re: Đáp án bài tập lý thuyết đồ thị đây   Thu Oct 13, 2011 1:38 am

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.
Về Đầu Trang Go down
http://vinhquangonline.tk/home
vboy_namioz19
Intel® Core i3 Processor
Intel® Core i3 Processor
avatar

Nam

Zodiac : Libra
Chinese zodiac : Goat
Tổng số bài gửi : 119
Việt Nam đồng : 2833118
Danh Vọng : 18
Birthday : 25/09/1991

Join date : 15/09/2010
Age : 26
Đến từ : Vinh Quang - Chiêm Hóa - Tuyên Quang
Job/hobbies : Non IT

Bài gửiTiêu đề: Re: Đáp án bài tập lý thuyết đồ thị đây   Thu Oct 13, 2011 1:41 am

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ỉ?
Về Đầu Trang Go down
http://vinhquangonline.tk/home
vboy_namioz19
Intel® Core i3 Processor
Intel® Core i3 Processor
avatar

Nam

Zodiac : Libra
Chinese zodiac : Goat
Tổng số bài gửi : 119
Việt Nam đồng : 2833118
Danh Vọng : 18
Birthday : 25/09/1991

Join date : 15/09/2010
Age : 26
Đến từ : Vinh Quang - Chiêm Hóa - Tuyên Quang
Job/hobbies : Non IT

Bài gửiTiêu đề: Re: Đáp án bài tập lý thuyết đồ thị đây   Thu Oct 13, 2011 10:44 am

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
Về Đầu Trang Go down
http://vinhquangonline.tk/home
phuonghoa_91
Intel® Core 2 Duo Processor
Intel® Core 2 Duo Processor
avatar

Nữ

Zodiac : Sagittarius
Chinese zodiac : Goat
Tổng số bài gửi : 57
Việt Nam đồng : 2767057
Danh Vọng : 7
Birthday : 03/12/1991

Join date : 09/10/2010
Age : 26
Đến từ : Chương Dương, Thường Tín, Hà Nội
Job/hobbies : Discovery World

Bài gửiTiêu đề: Re: Đáp án bài tập lý thuyết đồ thị đây   Thu Oct 13, 2011 11:58 pm

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:)
Về Đầu Trang Go down
vboy_namioz19
Intel® Core i3 Processor
Intel® Core i3 Processor
avatar

Nam

Zodiac : Libra
Chinese zodiac : Goat
Tổng số bài gửi : 119
Việt Nam đồng : 2833118
Danh Vọng : 18
Birthday : 25/09/1991

Join date : 15/09/2010
Age : 26
Đến từ : Vinh Quang - Chiêm Hóa - Tuyên Quang
Job/hobbies : Non IT

Bài gửiTiêu đề: Re: Đáp án bài tập lý thuyết đồ thị đây   Fri Oct 14, 2011 12:08 am

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ứ!
Về Đầu Trang Go down
http://vinhquangonline.tk/home
vboy_namioz19
Intel® Core i3 Processor
Intel® Core i3 Processor
avatar

Nam

Zodiac : Libra
Chinese zodiac : Goat
Tổng số bài gửi : 119
Việt Nam đồng : 2833118
Danh Vọng : 18
Birthday : 25/09/1991

Join date : 15/09/2010
Age : 26
Đến từ : Vinh Quang - Chiêm Hóa - Tuyên Quang
Job/hobbies : Non IT

Bài gửiTiêu đề: Re: Đáp án bài tập lý thuyết đồ thị đây   Fri Oct 14, 2011 12:08 am

Về Đầu Trang Go down
http://vinhquangonline.tk/home
phuonghoa_91
Intel® Core 2 Duo Processor
Intel® Core 2 Duo Processor
avatar

Nữ

Zodiac : Sagittarius
Chinese zodiac : Goat
Tổng số bài gửi : 57
Việt Nam đồng : 2767057
Danh Vọng : 7
Birthday : 03/12/1991

Join date : 09/10/2010
Age : 26
Đến từ : Chương Dương, Thường Tín, Hà Nội
Job/hobbies : Discovery World

Bài gửiTiêu đề: Re: Đáp án bài tập lý thuyết đồ thị đây   Fri Oct 14, 2011 12:53 am

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ế
Về Đầu Trang Go down
Hero_Kid
Intel® Core 2 Duo Processor
Intel® Core 2 Duo Processor
avatar

Nam

Zodiac : Cancer
Chinese zodiac : Goat
Tổng số bài gửi : 54
Việt Nam đồng : 2711038
Danh Vọng : 7
Birthday : 28/06/1991

Join date : 07/01/2011
Age : 26
Đến từ : Thái Bình

Bài gửiTiêu đề: Re: Đáp án bài tập lý thuyết đồ thị đây   Fri Oct 14, 2011 4:15 pm

cạnh đó là (2,3,3) mà các bạn
Về Đầu Trang Go down
vboy_namioz19
Intel® Core i3 Processor
Intel® Core i3 Processor
avatar

Nam

Zodiac : Libra
Chinese zodiac : Goat
Tổng số bài gửi : 119
Việt Nam đồng : 2833118
Danh Vọng : 18
Birthday : 25/09/1991

Join date : 15/09/2010
Age : 26
Đến từ : Vinh Quang - Chiêm Hóa - Tuyên Quang
Job/hobbies : Non IT

Bài gửiTiêu đề: Re: Đáp án bài tập lý thuyết đồ thị đây   Fri Oct 14, 2011 5:31 pm

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é!
Về Đầu Trang Go down
http://vinhquangonline.tk/home
mr.been
Intel® Core i3 Processor
Intel® Core i3 Processor
avatar

Nam

Zodiac : Leo
Chinese zodiac : Goat
Tổng số bài gửi : 149
Việt Nam đồng : 2932460
Danh Vọng : 11
Birthday : 16/08/1991

Join date : 14/09/2010
Age : 26
Đến từ : Vĩnh phúc Pro
Job/hobbies : test diễn đàn

Bài gửiTiêu đề: Re: Đáp án bài tập lý thuyết đồ thị đây   Fri Oct 14, 2011 9:54 pm

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

__________________________________________________
Về Đầu Trang Go down
chjecla_dangyeu
Intel® Core 2 Duo Processor
Intel® Core 2 Duo Processor
avatar

Nữ

Zodiac : Virgo
Chinese zodiac : Goat
Tổng số bài gửi : 90
Việt Nam đồng : 2851093
Danh Vọng : 8
Birthday : 13/09/1991

Join date : 14/09/2010
Age : 26
Đến từ : Thanh Hóa quê choa
Job/hobbies : Uống trà đá , ăn crem.....Thích những gì mọi người thích.

Bài gửiTiêu đề: Re: Đáp án bài tập lý thuyết đồ thị đây   Sat Oct 15, 2011 12:17 am

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à

__________________________________________________
Về Đầu Trang Go down
hanhsn
Intel® Pentium IV Processor
Intel® Pentium IV Processor
avatar

Nữ

Zodiac : Taurus
Chinese zodiac : Goat
Tổng số bài gửi : 15
Việt Nam đồng : 2424015
Danh Vọng : 3
Birthday : 23/04/1991

Join date : 11/09/2011
Age : 27
Đến từ : Hưng Yên
Job/hobbies : Sinh Viên

Bài gửiTiêu đề: Re: Đáp án bài tập lý thuyết đồ thị đây   Sat Oct 15, 2011 11:25 am

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ỉ?
Về Đầu Trang Go down
mr.been
Intel® Core i3 Processor
Intel® Core i3 Processor
avatar

Nam

Zodiac : Leo
Chinese zodiac : Goat
Tổng số bài gửi : 149
Việt Nam đồng : 2932460
Danh Vọng : 11
Birthday : 16/08/1991

Join date : 14/09/2010
Age : 26
Đến từ : Vĩnh phúc Pro
Job/hobbies : test diễn đàn

Bài gửiTiêu đề: Re: Đáp án bài tập lý thuyết đồ thị đây   Sat Oct 15, 2011 9:33 pm

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

__________________________________________________
Về Đầu Trang Go down
Sponsored content




Bài gửiTiêu đề: Re: Đáp án bài tập lý thuyết đồ thị đây   

Về Đầu Trang Go down
 
Đáp án bài tập lý thuyết đồ thị đây
Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» Bài bình luận của thuyền trưởng Tiếu Văn Kinh
» Điều động tàu khi có cháy
» Cuộc sống sau này của anh em nè, vào đọc cho vui nhé
» Basic Ship Theory - Lý thuyết tàu cơ bản
» Hướng dẫn đổi hộ chiếu phổ thông và hộ chiếu thuyền viên sắp hết hạn

Permissions in this forum:Bạn không có quyền trả lời bài viết
¸.•'´¯) ¸,ؤ°``°¤Ø,¸(¯`'•.¸Tin Trắc Địa k54¸.•'´¯) ¸,ؤ°``°¤Ø,¸(¯`'•.¸ :: ¸.•'´¯) ¸,ø¤°``°¤ø,¸(¯`'•.¸Học gì kì này¸.•'´¯) ¸,ø¤°``°¤ø,¸(¯`'•.¸ :: Kì 5 năm học 2011 - 2012 :: Lý thuyết đồ thị cho Tin học-
Chuyển đến