zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

PHÂN TÍCH ĐỘ PHỨC TẠP CÁC GIẢI THUẬT ĐỒ THỊ

Chia sẻ: No Comment | Ngày: | Loại File: PPT | Số trang:81

Báo xấu

191
lượt xem 35
download

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

TÀI LIỆU THAM KHẢO KỸ THUẬT LẬP TRÌNH - PHÂN TÍCH ĐỘ PHỨC TẠP CÁC GIẢI THUẬT ĐỒ THỊ

Chủ đề:

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

Lưu

Nội dung Text: PHÂN TÍCH ĐỘ PHỨC TẠP CÁC GIẢI THUẬT ĐỒ THỊ

1 CHƯƠNG 4 P HÂN TÍCH ĐỘ PHỨC TẠP CÁC GIẢI THUẬT ĐỒ THỊ
Nội dung 2 Định nghĩa đồ thị  Các giải thuật duyệt đồ thị  Giải thuật trên đồ thị có trọng số  Giải thuật trên đồ thị có hướng 
Định nghĩa đồ thị 3
Phân loại đồ thị 4
Biểu diễn đồ thị trên máy tính 5
Biểu diễn đồ thị trên máy tính 6
Biểu diễn đồ thị trên máy tính 7
Biểu diễn đồ thị trên máy tính 8
Biểu diễn đồ thị trên máy tính 9
Biểu diễn đồ thị trên máy tính 10
Biểu diễn đồ thị trên máy tính 11
Biểu diễn đồ thị trên máy tính 12
Biểu diễn đồ thị trên máy tính 13
Biểu diễn đồ thị trên máy tính 14
Các giải thuật duyệt đồ thị 15 Tìm kiếm theo chiều rộng   Tìm kiếm theo chiều sâu  Tìm cây bao trùm nhỏ nhất  Tìm đường đi ngắn nhất
Nội dung bài toán tìm kiếm Cho đồ thị G=(V,E) và một đỉnh s. Xuất phát từ  đỉnh s, hãy duyệt qua tất cả các đỉnh của đồ thị Kí hiệu:  V(G)=tập các đỉnh của G, E(G)=tập các cạnh của G.  Hàm Color(u) chỉ trạng thái các đỉnh trong quá trình tìm kiếm. Color(u) nhận một trong 3 giá trị : đầu, WHITE, GRAY, BLACK. Lúc Color(u)=WHITE nghĩa là chưa được xét, với những đỉnh u bắt đầu xét, Color(u)=GRAY, khi u đã xét xong Color(u)=BLACK
Tìm kiếm theo chiều rộng (Breadth-First Search-BFS) 17 Ý tưởng thuật toán  Bắt đầu tìm kiếm từ đỉnh s cho trước tuỳ ý  Tại thời điểm đã tìm thấy u, thuật toán tiếp tục tìm kiếm tập tất cả các đỉnh kề với u  Thực hiện quá trình này cho các đỉnh còn lại
Tìm kiếm theo chiều rộng (Breadth-First Search-BFS) 18 Ý tưởng thuật toán  Dùng một hàng đợi để duy trì trật tự tìm kiếm theo chiều rộng  Dùng các màu để không lặp lại các đỉnh tìm kiếm  Dùng một mảng để xác định đường đi ngắn nhất từ s đến các đỉnh đã được tìm kiếm  Dùng một mảng để lưu trữ đỉnh đi trước của đỉnh được tìm kiếm
Tìm kiếm theo chiều rộng (Breadth-First Search-BFS) 19 Procedure BFS(G,s) for each u ∈ V[G] do 1. 2. color[u]:= WHITE;Prev(u)=Null; color[s]:=GRAY; 3. Q:= {s} While Q # ∅ do 4. u:= Head(Q); /*lấy u là phần tử đứng đầu 5. hàng đợi để xét*/ 6. For each v ∈ Adj(u) 7. if color(v)= WHITE then 8. color(v):=GRAY; Prev(v):= u; ENQUEUE(Q,v);/*đặt v vào cuối hàng đợi*/ 9. 10. DeQueue(Q,u);/* Gỡ u khỏi hàng đợi */ 11. Color(u):= BLACK;
Tìm kiếm theo chiều rộng (Breadth-First Search-BFS) Ví d ụ: Adj(v)∩ Đỉnh trắng Đỉnh Queue v BFS(A) Trắng đen D A A A B,C,D,E B,C,D,E,F A E B,C,D,E B F B B F C C,D,E C F F C D,E,F D D E,F E E F F F Rỗng

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.