TAILIEUCHUNG - 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Ị | PHÂN TÍCH ĐỘ PHỨC TẠP CÁC GIẢI THUẬT ĐỒ THỊ CHƯƠNG 4 Nội dung Đị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ị Phân loại đồ thị Biểu diễn đồ thị trên máy tính Biểu diễn đồ thị trên máy tính Biểu diễn đồ thị trên máy tính Biểu diễn đồ thị trên máy tính Biểu diễn đồ thị trên máy tính Biểu diễn đồ thị trên máy tính Biểu diễn đồ thị trên máy tính Biểu diễn đồ thị trên máy tính Biểu diễn đồ thị trên máy tính Biểu diễn đồ thị trên máy tính Các giải thuật duyệt đồ thị 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ị : WHITE, GRAY, BLACK. Lúc đầu, 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) Ý 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) Ý 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) Procedure BFS(G,s) for each u V[G] do color[u]:= WHITE;Prev(u)=Null; color[s]:=GRAY; Q:= {s} While Q # do u:= Head(Q); /*lấy u là phần tử đứng

• Kỹ thuật lập trình
• thủ thuật lập trình
• lập trình căn bản
• thiết kế giải thuật
• thuật toán
• cấu trúc giải thuật
• kỹ thuật phần mềm
• chương trình lập trình
• kỹ thuật máy tính
• giáo trình lập trình
• lập trình hướng đối tượng
• tài liệu lập trình
• chuyên ngành lập trình
• tổng quan về lập trình
• ngôn ngữ lập trình
• lập trình máy tính
• phần mềm máy tính
• code lập trình
• kinh nghiệm lập trình
• mẹo lập trình
• lập trình C++
• thủ thuật lập trình iphone
• lập trình iphone
• cài đặt iphone
• thủ thuật iphone
• ebook lập trình iphonethủ thuật lập trình iphone
• ebook lập trình iphone
• lập trình Visual C++
• Lập trình C trên Windows
• lập trình java
• Lập trình mạng bằng java
• Lập trình nâng cao
• thủ thuật hệ điều hành
• tìm hiểu hệ điều hành
• thủ thuật windows
• lập trình windows
• lập trình ứng dụng
• mẹo hay cho lập trình
• bí quyết lập trình