intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Cấu trúc dữ liệu và giải thuật - Chương 18

Chia sẻ: Chu Quang Chien | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST
Báo xấu
110
lượt xem 12
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo dành cho giáo viên, sinh viên chuyên ngành công nghệ thông tin - Giáo trình cấu trúc dữ liệu và giải thuật do các giáo viên trường đại học hoa sen biên soạn.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Cấu trúc dữ liệu và giải thuật - Chương 18

  1. Minimum spanning tree Minimum Khái ni m: - Cây bao trùm t i thi u MST (minimum spanning tree) c a m t th có tr ng s là m t t p h p các c nh k t n i t t c các nh sao cho t ng tr ng s c a các c nh là nh nh t - MST không nh t thi t là duy nh t trong m t th
  2. Minimum spanning tree Minimum Ví d :
  3. Thu t toán Dijkstra-Prim Thu to Gi i thi u: - Thu t toán do Edsger Dijkstra và R.C. Prim tìm ra vào năm 1950 m t cách cl p - Gi i thu t Prim dùng gi i bài toán cây bao trùm t i thi u. - Gi i thu t này s d ng chi n lư c gi i m t bài toán t i ưu hóa: gi i thu t tham lam (greedy): T i m i bư c c a gi i thu t, ta ph i ch n m t trong m t s kh năng l a ch n. Chi n lư c tham lam xu t vi c l a ch n kh năng t t nh t t i lúc ó.
  4. Thu t toán Dijkstra-Prim Thu to Gi i thi u: - M t chi n lư c như v y thư ng không m b o em l i l i gi i t i ưu toàn c c cho các bài toán. - Tuy nhiên, i v i bài toán MST, gi i thu t tham lam có th em l i MST v i t ng tr ng s t i thi u
  5. Thu t toán Dijkstra-Prim Thu to Gi i thu t: - Ch n m t nh A b t u trong th - Xây d ng m t t p h p Q bao g m các nh ư c n i t nh A - Ch n nh ti p theo trong t p Q sao có c nh t nh A n là nh nh t - Ti p t c thêm vào Q nh ng nh b t u t nh th 2 - Vòng l p ti p t c cho n khi t t c các nh ư c duy t qua
  6. Thu t toán Dijkstra-Prim Thu to Ví d : L={a,b,c,d,e,f,g,h,i} // T p các nh chưa xét MST // Cây khung Q //Hàng i g m các nh ư c n i v i các nh trong cây khung
  7. Thu t toán Dijkstra-Prim Thu to Ví d : MST Q L R ng R ng a,b,c,d,e,f,g,h,i a b,h c,d,e,f,g,i a,b h,c d,e,f,g,i 4
  8. Thu t toán Dijkstra-Prim Thu to Ví d : MST Q L a,b h,c d,e,f,g,i 4 a,b,c h,d,f,i e,g 12
  9. Thu t toán Dijkstra-Prim Thu to Ví d : MST Q L a,b,c h,d,f,i e,g 12 a,b,c,i h,d,f,g e 14
  10. Thu t toán Dijkstra-Prim Thu to Ví d : MST Q L a,b,c,i h,d,f,g e 14 a,b,c,i,f h,d,g,e R ng 18
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
464=>2