¸.•'´¯) ¸,ؤ°``°¤Ø,¸(¯`'•.¸Tin Trắc Địa k54¸.•'´¯) ¸,ؤ°``°¤Ø,¸(¯`'•.¸
Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.
¸.•'´¯) ¸,ؤ°``°¤Ø,¸(¯`'•.¸Tin Trắc Địa k54¸.•'´¯) ¸,ؤ°``°¤Ø,¸(¯`'•.¸
¸.•'´¯) ¸,ؤ°``°¤Ø,¸(¯`'•.¸Tin Trắc Địa k54¸.•'´¯) ¸,ؤ°``°¤Ø,¸(¯`'•.¸
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ế.
Được sửa bởi thank0bk54 ngày Tue Oct 11, 2011 10:00 pm; sửa lần 1.
hanhsn Intel® Pentium IV Processor
Zodiac : Chinese zodiac : Tổng số bài gửi : 15 Việt Nam đồng : 4637015 Danh Vọng : 3 Birthday : 23/04/1991
Join date : 11/09/2011 Age : 33 Đến từ : Hưng Yên Job/hobbies : Sinh Viên
Tiê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
thank0bk54 Intel® Core 2 Duo Processor
Zodiac : Chinese zodiac : Tổng số bài gửi : 97 Việt Nam đồng : 5003121 Danh Vọng : 3 Birthday : 30/11/1991
Join date : 06/10/2010 Age : 32 Đến từ : Bắc Giang Job/hobbies : Freelancer
Tiê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
phuonghoa_91 Intel® Core 2 Duo Processor
Zodiac : Chinese zodiac : Tổng số bài gửi : 57 Việt Nam đồng : 4980057 Danh Vọng : 7 Birthday : 03/12/1991
Join date : 09/10/2010 Age : 32 Đến từ : Chương Dương, Thường Tín, Hà Nội Job/hobbies : Discovery World
Tiê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.
vboy_namioz19 Intel® Core i3 Processor
Zodiac : Chinese zodiac : Tổng số bài gửi : 119 Việt Nam đồng : 5046118 Danh Vọng : 18 Birthday : 25/09/1991
Join date : 15/09/2010 Age : 32 Đến từ : Vinh Quang - Chiêm Hóa - Tuyên Quang Job/hobbies : Non IT
Tiê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
vboy_namioz19 Intel® Core i3 Processor
Zodiac : Chinese zodiac : Tổng số bài gửi : 119 Việt Nam đồng : 5046118 Danh Vọng : 18 Birthday : 25/09/1991
Join date : 15/09/2010 Age : 32 Đến từ : Vinh Quang - Chiêm Hóa - Tuyên Quang Job/hobbies : Non IT
Tiê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.
vboy_namioz19 Intel® Core i3 Processor
Zodiac : Chinese zodiac : Tổng số bài gửi : 119 Việt Nam đồng : 5046118 Danh Vọng : 18 Birthday : 25/09/1991
Join date : 15/09/2010 Age : 32 Đến từ : Vinh Quang - Chiêm Hóa - Tuyên Quang Job/hobbies : Non IT
Tiê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ỉ?
vboy_namioz19 Intel® Core i3 Processor
Zodiac : Chinese zodiac : Tổng số bài gửi : 119 Việt Nam đồng : 5046118 Danh Vọng : 18 Birthday : 25/09/1991
Join date : 15/09/2010 Age : 32 Đến từ : Vinh Quang - Chiêm Hóa - Tuyên Quang Job/hobbies : Non IT
Tiê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
phuonghoa_91 Intel® Core 2 Duo Processor
Zodiac : Chinese zodiac : Tổng số bài gửi : 57 Việt Nam đồng : 4980057 Danh Vọng : 7 Birthday : 03/12/1991
Join date : 09/10/2010 Age : 32 Đến từ : Chương Dương, Thường Tín, Hà Nội Job/hobbies : Discovery World
Tiê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:)
vboy_namioz19 Intel® Core i3 Processor
Zodiac : Chinese zodiac : Tổng số bài gửi : 119 Việt Nam đồng : 5046118 Danh Vọng : 18 Birthday : 25/09/1991
Join date : 15/09/2010 Age : 32 Đến từ : Vinh Quang - Chiêm Hóa - Tuyên Quang Job/hobbies : Non IT
Tiê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ứ!
vboy_namioz19 Intel® Core i3 Processor
Zodiac : Chinese zodiac : Tổng số bài gửi : 119 Việt Nam đồng : 5046118 Danh Vọng : 18 Birthday : 25/09/1991
Join date : 15/09/2010 Age : 32 Đến từ : Vinh Quang - Chiêm Hóa - Tuyên Quang Job/hobbies : Non IT
Tiêu đề: Re: Đáp án bài tập lý thuyết đồ thị đây Fri Oct 14, 2011 12:08 am
phuonghoa_91 Intel® Core 2 Duo Processor
Zodiac : Chinese zodiac : Tổng số bài gửi : 57 Việt Nam đồng : 4980057 Danh Vọng : 7 Birthday : 03/12/1991
Join date : 09/10/2010 Age : 32 Đến từ : Chương Dương, Thường Tín, Hà Nội Job/hobbies : Discovery World
Tiê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ế
Hero_Kid Intel® Core 2 Duo Processor
Zodiac : Chinese zodiac : Tổng số bài gửi : 54 Việt Nam đồng : 4924038 Danh Vọng : 7 Birthday : 28/06/1991
Join date : 07/01/2011 Age : 32 Đến từ : Thái Bình
Tiê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
vboy_namioz19 Intel® Core i3 Processor
Zodiac : Chinese zodiac : Tổng số bài gửi : 119 Việt Nam đồng : 5046118 Danh Vọng : 18 Birthday : 25/09/1991
Join date : 15/09/2010 Age : 32 Đến từ : Vinh Quang - Chiêm Hóa - Tuyên Quang Job/hobbies : Non IT
Tiê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é!
mr.been Intel® Core i3 Processor
Zodiac : Chinese zodiac : Tổng số bài gửi : 149 Việt Nam đồng : 5145460 Danh Vọng : 11 Birthday : 16/08/1991
Join date : 14/09/2010 Age : 32 Đến từ : Vĩnh phúc Pro Job/hobbies : test diễn đàn
Tiê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)
chjecla_dangyeu Intel® Core 2 Duo Processor
Zodiac : Chinese zodiac : Tổng số bài gửi : 90 Việt Nam đồng : 5064093 Danh Vọng : 8 Birthday : 13/09/1991
Join date : 14/09/2010 Age : 32 Đế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.
Tiê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à
hanhsn Intel® Pentium IV Processor
Zodiac : Chinese zodiac : Tổng số bài gửi : 15 Việt Nam đồng : 4637015 Danh Vọng : 3 Birthday : 23/04/1991
Join date : 11/09/2011 Age : 33 Đến từ : Hưng Yên Job/hobbies : Sinh Viên
Tiê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ỉ?
mr.been Intel® Core i3 Processor
Zodiac : Chinese zodiac : Tổng số bài gửi : 149 Việt Nam đồng : 5145460 Danh Vọng : 11 Birthday : 16/08/1991
Join date : 14/09/2010 Age : 32 Đến từ : Vĩnh phúc Pro Job/hobbies : test diễn đàn
Tiêu đề: Re: Đáp án bài tập lý thuyết đồ thị đây Sat Oct 15, 2011 9:33 pm