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

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.
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật - Chương 18 Minimum spanning tree MinimumKhái ni m:- Cây bao trùm t i thi u MST (minimum spanningtree) c a m t th có tr ng s là m t t p h p cácc nh k t n i t t c các nh sao cho t ng tr ng s c acác c nh là nh nh t- MST không nh t thi t là duy nh t trong m t th Minimum spanning tree MinimumVí d : Thu t toán Dijkstra-Prim Thu toGi 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 ó. Thu t toán Dijkstra-Prim Thu toGi 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 Thu t toán Dijkstra-Prim Thu toGi 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 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étMST // Cây khungQ //Hàng i g m các nh ư c n i v i các nh trong cây khung Thu t toán Dijkstra-Prim Thu toVí 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 Thu t toán Dijkstra-Prim Thu toVí d : MST Q L a,b h,c d,e,f,g,i 4 a,b,c h,d,f,i e,g 12 Thu t toán Dijkstra-Prim Thu toVí d : MST Q L a,b,c h,d,f,i e,g 12 a,b,c,i h,d,f,g e 14 Thu t toán Dijkstra-Prim Thu toVí 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