Tìm cây khung nhỏ nhất bằng thuật toán prim

Dựa vào phần mã giả mình đã viết code như sau,mình gồm chú ham mê cho chúng ta rồi,các bạn xem xem có hiểu ko nhé,nếu gồm thắc đừng quên comment bạn nhé,nếu mình chậm vấn đáp thì tương tác facebook mình hổ trợ trực tiếp luôn nè.

Bạn đang xem: Tìm cây khung nhỏ nhất bằng thuật toán prim

Một ví dụ nhỏ tuổi mình tham khảo trên wiki,các các bạn xem nhằm hiểu hơn về kiểu cách thức buổi giao lưu của thuật toán nhé!

Hình minh họaUCạnh (u,v)V UMô tả

	D	(D,A) = 5 V(D,B) = 9(D,E) = 15(D,F) = 6	A,B,C,E,F,G	Chọn một giải pháp tùy ý đỉnh D là đỉnh bắt đầu. Những đỉnh A, B, E và F số đông được nối trực tiếp cho tới D bởi cạnh của vật thị. A là đỉnh sát D nhất cần ta chọn A là đỉnh đồ vật hai của cây cùng thêm cạnh AD vào cây.
	A,D,F	(D,B) = 9(D,E) = 15(A,B) = 7 V(F,E) = 8(F,G) = 11	B,C,E,G	Thuật toán liên tục tương từ như bước trước. Chọn đỉnh B có khoảng cách tới A bởi 7. Xem thêm: Những Bức Ảnh Đánh Lừa Thị Giác Bảo Đảm Sẽ Khiến Bạn Phải Kinh Ngạc
	A,B,D,E,F	(B,C) = 8(D,B) = 9 chu trình(D,E) = 15 chu trình(E,C) = 5 V(E,G) = 9(F,E) = 8 chu trình(F,G) = 11	C,G	Ở đoạn này ta chọn giữa C cùng G. C có khoảng cách tới E bởi 5, và G có khoảng cách tới E bằng 9. Lựa chọn C cùng cạnh EC.
	A,B,C,D,E,F,G	(B,C) = 8 chu trình(D,B) = 9 chu trình(D,E) = 15 chu trình(F,E) = 8 chu trình(F,G) = 11 chu trình		Hiện giờ tất cả các đỉnh đã nằm trong cây cùng cây bao trùm nhỏ độc nhất được tô màu xanh lá cây lá cây. Tổng trọng số của cây là 39.

Chúc chúng ta hoàn thành tốt bài tập này nhé!

để ý là thuật toán trên mình tự code nên chắc hẳn rằng không thể không có sai sót cần mong các bạn thông cảm và chỉ dùng làm tham khảo thôi nhé. giấy phép Creative Commons Attribution-ShareAlike 4.0 thế giới .