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

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Ị
Nội dung trích xuất từ tài liệu:
PHÂN TÍCH ĐỘ PHỨC TẠP CÁC GIẢI THUẬT ĐỒ THỊ 1CHƯƠNG 4 P HÂN TÍCH ĐỘ PHỨC TẠP CÁC GIẢI THUẬT ĐỒ THỊ Nộidung2 Đị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  Địnhnghĩađồthị3 Phânloạiđồthị4 Biểudiễnđồthịtrênmáytính5 Biểudiễnđồthịtrênmáytính6 Biểudiễnđồthịtrênmáytính7 Biểudiễnđồthịtrênmáytính8 Biểudiễnđồthịtrênmáytính9 Biểudiễnđồthịtrênmáytính10 Biểudiễnđồthịtrênmáytính11 Biểudiễnđồthịtrênmáytính12 Biểudiễnđồthịtrênmáytính13 Biểudiễnđồthịtrênmáytính14 Cácgiảithuậtduyệtđồthị15 Tìmkiếmtheochiềurộng   Tìmkiếmtheochiềusâu  Tìmcâybaotrùmnhỏnhất  TìmđườngđingắnnhấtNộidungbàitoántìmkiế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ìmkiếmtheochiềurộ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ìmkiếmtheochiềurộ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ìmkiếmtheochiềurộ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ìmkiếmtheochiềurộ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 BB F C C,D,E C F F C D,E,F D D E,F E E F F F Rỗng