09HCB

Trang chủ 09HCB- Lớp Hoàn Chỉnh Đại Học Khoá 2009-2011
 
Trang ChínhTrang Chính  GalleryGallery  Tìm kiếmTìm kiếm  Đăng kýĐăng ký  Đăng NhậpĐăng Nhập  

Share
 

 So sánh Kruskal và Prim

Go down 
Tác giảThông điệp
ngocthai

ngocthai

Tổng số bài gửi : 60
Join date : 17/03/2010

So sánh Kruskal và Prim Empty
Bài gửiTiêu đề: So sánh Kruskal và Prim   So sánh Kruskal và Prim Empty21/5/2010, 10:46 am

- Do thuật toán Kruskal làm việc trên các cạnh nên sẽ kém hiệu quả nếu có quá nhiều cạnh? như các đồ thị dày (số cạnh m ≈ n(n-1)/2).
- Đối nghịch với Kruskal, thuật toán Prim làm việc trên các đỉnh, sẽ hiệu quả hơn với các đồ thị dày. Có thế thấy đa số các đồ thị trong thực tế có số đỉnh không lớn còn số cạnh rất lớn nên Prim tỏ ra hiệu quả hơn và?đắt giá? hơn Kruskal, mặc dù cài đặt có phức tạp hơn. Ngoại lệ, trong các trường hợp số cạnh rất ít còn số đỉnh rất nhiều thì Prim kém hiệu quả hơn Kruskal.

(nguồn: http://forum.uitstudent.com/showthread.php?7399-C%C3%A2y-khung-nh%E1%BB%8F-nh%E1%BA%A5t-v%E1%BB%9Bi-thu%E1%BA%ADt-to%C3%A1n-Kruskal-v%C3%A0-Prim)
Về Đầu Trang Go down
 
So sánh Kruskal và Prim
Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
09HCB :: Lưu trữ :: HK1 :: LTDT-
Chuyển đến