THUẬT TOÁN Dijkstra-Prim

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

Báo xấu

360
lượt xem 51
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo tài liệu 'thuật toán dijkstra-prim', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Lưu

Nội dung Text: THUẬT TOÁN Dijkstra-Prim

Thu t toán Dijkstra-Prim Thu to Ví d : MST Q L a,b,c,i,f h,d,g,e R ng 18 a,b,c,i,f,g h,d,e R ng 20
Thu t toán Dijkstra-Prim Thu to Ví d : MST Q L a,b,c,i,f,g h,d,e R ng 20 a,b,c,i,f,g,h d,e R ng 21
Thu t toán Dijkstra-Prim Thu to Ví d : MST Q L a,b,c,i,f,g,h d,e R ng 21 a,b,c,i,f,g,h,d e R ng 28
Thu t toán Dijkstra-Prim Thu to Ví d : MST Q L a,b,c,i,f,g,h,d e R ng 28 a,b,c,i,f,g,h,d,e R ng R ng 36
Thu t toán Dijkstra-Prim Thu to ánh giá gi i thu t: - ph c t p c a gi i thu t Prim ph thu c vào cách th c hi n ưu tiên hàng i Q - N u Q ư c th c hi n như m t heap nh phân thì th i gian tính toán c a gi i thu t là O (E lgV)
Thu t toán Kruskal Thu to Gi i thi u: - Khác v i gi i thu t Dijkstra-Prim b t u v i 1 nh b t kì ê xây d ng MST. Thu t toán Kruskal t p trung vào các c nh c a th Gi i thu t: - B t u v i MST r ng - Thêm vào MST các c nh có th t tăng d n theo tr ng s cho n khi t t c các nh ư c k t n i
Thu t toán Kruskal Thu to Ví d : MST V R ng A,B,C,D,E,F,G FD A,B,C,E,G FD,AB C,E,G FD,AB,BE C,G FD,AB,BE,AC G FD,AB,BE,AC,AF G FD,AB,BE,AC,AF,DG R ng
Thu t toán Kruskal Thu to ph c t p c a gi i thu t: - Thu t toán Kruskal có ph c t p là O(E lgE) Bài t p: S d ng thu t toán Dijkstra-Prim tìm MST c a th sau, b t u b t node C. Trình các bư c bày y
Thu t toán Kruskal Thu to Bài t p: S d ng thu t toán Krusal tìm MST c a th sau.Trình bày y các bư c
Ư NG I NG N NH T NG NH