TAILIEUCHUNG - Giáo trình lý thuyết đồ thị - Bài 11

Các thuật toán duyệt đồ thị Phép duyệt đồ thị là một cách liệt kê tất cả các đỉnh của đồ thị này thành một danh sách tuyến tính. Hay nói một cách khác, phép duyệt đồ thị cho ta một cách “đi qua” tất cả các đỉnh của đồ thị để truy nhập, thêm bớt thông tin ở các đỉnh của đồ thị đó. Phép duyệt đồ thị không phụ thuộc vào hướng của các cạnh. Do vậy, với đồ thị có hướng thì ta vô hướng hoá trước khi duyệt. . | BÀI 11 Chương 6 Các thuật toán duyệt đồ thị Phép duyệt đồ thị là một cách liệt kê tất cả các đỉnh của đồ thị này thành một danh sách tuyến tính. Hay nói một cách khác phép duyệt đồ thị cho ta một cách đi qua tất cả các đỉnh của đồ thị để truy nhập thêm bớt thông tin ở các đỉnh của đồ thị đó. Phép duyệt đồ thị không phụ thuộc vào hướng của các cạnh. Do vậy với đồ thị có hướng thì ta vô hướng hoá trước khi duyệt. . Các thuật toán duyệt đồ thị . Thuật toán duyệt đồ thị Giả sử G V E là đồ thị đã cho và Vo là một đỉnh nào đó của G. Ký hiệu DS là một cấu trúc dữ liệu kiểu danh sách dùng để chứa các đỉnh. 1 Khởi đầu DS x0 2 Lấy đỉnh X ra khỏi đầu DS 3 Duyệt đỉnh X 4 Nạp các đỉnh của F x vào DS 5 Nếu DS 0 thì quay lên bước 2 6 Dừng . Duyệt theo chiều sâu Depth-First Search Nếu trong thuật toán trên danh sách DS được tổ chức theo kiểu stack danh sách vào sau - ra trước - LIFO thì ta có phương pháp duyệt theo chiều sâu. Trong phương pháp này mỗi lần duyệt một đỉnh ta duyệt đến tận cùng mỗi nhánh rồi mới chuyển sang duyệt nhánh khác. Giả sử G V E là một đồ thị vô hướng. Ta bắt đầu duyệt từ một đỉnh x0 nào đó của đồ thị. Sau đó chọn X là đỉnh kề nào đó của Xo và lặp lại quá trình duyệt đối với đỉnh X. Giả sử ta đang xét đỉnh X. Nếu trong số các đỉnh kề với X ta tìm được đỉnh y chưa được duyệt thì ta sẽ xét đỉnh này và bắt đầu từ đó ta tiếp tục quá trình duyệt. Ngược lại nếu không còn đỉnh nào kề với x chưa được duyệt thì ta nói rằng đỉnh x đã duyệt xong và quay trở lại tiếp tục duyệt từ đỉnh mà từ đó ta đến được đỉnh x. Nếu quay trỏ lại đúng đỉnh x0 thì phép duyệt kết thúc. Thuật toán Duyệt đồ thị theo chiều sâu Dữ liệu Biểu diễn mảng DK các danh sách kề của đồ thị vô hướng G. Kết quả Danh sách các đỉnh của đồ thị G. 1 procedure D_SAU v 2 begin 3 Thăm_đỉnh v 4 Duyet v true 5 for u G DK v do 6 if Duyet u then D_SAU u 7 end 8 BEGIN 9 for v G V do Duyet v false 10 for v G V do 11 if Duyet v then D_SAU v 12 END. Chương trình chính Độ phức tạp của thật toán là O n

• Toán học
• Chu trình Hamilton
• thuật toán
• đồ thị
• ứng dụng cây
• hàm trên đồ thị
• Lý thuyết đồ thị
• Đường đi Hamilton
• Đồ thị Hamilton
• Định nghĩa về chu trình Hamilton
• Định nghĩa về đường đi Hamilton
• Đường Hamilton
• bài toán mã đi tuần
• chu trình vô hướng hamilton
• Luận án Tiến sĩ Toán học
• Luận án Tiến sĩ
• Cơ sở toán học cho tin học
• Thuật toán đa thức xác định chu trình Hamilton
• Bài giảng Lý thuyết đồ thị
• Đồ thị Euler
• Kiểm tra đồ thị Hamilton
• Bài toán người du lịch
• Bài toán tối ưu tổ hợp
• Đường Hamilton
• Thuật toán nhánh cận giải TSP
• Bài toán người du lịch và thuật toán nhánh cận
• Bài toán tối ưu liên quan đến đường Hamilton
• Đồ thị tách cực
• Đồ thị tách cực phi Hamilton tối đại
• Bậc cực tiểu
• Chu trình euler
• thuật toán tìm chu trình
• đồ thị liên thông
• Bài toán lý thuyết đồ thị
• Bài toán luông
• toán rời rạc
• bài tập học phần
• Đường đi đồ thị
• Đồ thị phẳng
• Bài toán tô màu đồ thị
• Tài liệu Thực hành
• Đồ thị Chu trình
• Lý thuyết đồ thị chu trình
• Đường đi Euler
• Đồ thị ơ2= N
• Đồ thị đơn
• Bài toán HC
• Thuật toán đa thức
• Xây dựng thuật toán đa thức
• Đồ thị 2 phần
• Đồ thị đầy đủ
• Đồ thị rỗng
• tài liệu toán học
• phép toán hedetniemi
• bài giảng toán học
• các bài toán về đường đi
• Bài giảng Toán rời rạc
• Thuật toán Dijkstra
• giáo trình đồ thị
• tài liệu về đồ thị
• ứng dụng của đồ thị
• Đường đi trên đồ thị
• Bài toán đường đi tốt nhất
• Bài giảng Cấu trúc rời rạc
• Cấu trúc rời rạc
• Chu trình và đường đi Euler
• Chu trình và đường đi Hamilton